For each of the following statements, mark in the answer sheets whether the statement istrue or false.(a) Let f and g be positive functions. Then, f (n) + g(n) ∈ O(n) implies that f ∈ O(n)and g ∈ O(n).(b) There exist functions f, g ∈ Ω(n) such that f − g ∈ Ω(g) and 2g − f ∈ Ω(f ).

Prove the following assertions by using the definitions of the notations in-volved, or disprove them by giving a specific counterexample.a. If t (n) ∈ O(g(n)), then g(n) ∈ (t (n)).b. (αg(n)) = (g(n)), where α > 0.c. (g(n)) = O(g(n)) ∩ (g(n)).d. For any two nonnegative functions t (n) and g(n) defined on the set ofnonnegative integers, either t (n) ∈ O(g(n)), or t (n) ∈ (g(n)), or both

The following statements are equivalent:1 f ∈ Ω(g )2 g ∈ O(f )Proof. → Exercise

Which of the following is false on two positive functions f and g?A. if f = ⇥ (g), then g = ⌦ (f )B. if f = ⇥ (g), then g = ⇥ (f )C. if f = ⇥ (g), then g = O(f )D. none of them.

A) Big-O notation and loop invariants1. Let g(n) be a function. For each of the following statements, mark in the answer sheetswhether it is correct (true = correct, false = incorrect).(a) Θ(g) = {f (n) : There exist positive constants c1, c2 and n0 such that0 ≤ c1 · g(n) ≤ f (n) ≤ c2 · g(n), for all n ≥ n0}(b) Θ(g) = {f (n) : There exist positive constants c1, c2 and n0 such that0 ≤ c1 · f (n) ≤ g(n) ≤ c2 · f (n), for all n ≥ n0}(c) Θ(g) = O(g) ∩ Ω(g)

1. Let g(n) be a function. For each of the following statements, mark in the answer sheetswhether it is correct (true = correct, false = incorrect).(a) Θ(g) = {f (n) : There exist positive constants c1, c2 and n0 such that0 ≤ c1 · g(n) ≤ f (n) ≤ c2 · g(n), for all n ≥ n0}(b) Θ(g) = {f (n) : There exist positive constants c1, c2 and n0 such that0 ≤ c1 · f (n) ≤ g(n) ≤ c2 · f (n), for all n ≥ n0}(c) Θ(g) = O(g) ∩ Ω(g)