For each of the following statements, mark in the answer sheets whether the statement istrue or false.(a) n2 ∈ O(n)(b) 22 ∈ O(1)(c) n2 − 4n ∈ O(15n)(d) 4 log n + 10 log2 n ∈ O(log2 n)(e) 3n ∈ O(n!)

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 ).

6. Give as good a big-O estimate as possible for each of these functions.a) (n2 + 8)(n + 1) b) (n log n + n2)(n3 + 2) c) (n! + 2n)(n3 + log(n2 + 1))

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)

2. Determine whether each of these functions is O(x2).a) f (x) = 17x + 11 b) f (x) = x2 + 1000 c) f (x) = x log xd) 42xf x  e) 2xf x  f) ) f (x) = (x3 + 2x)/(2x + 1)

(15 points) Prove that the following assertion is true for all values of n ≥ n0. Identify both n0 and c.2n + 5∈ O(n2)