Consider functions f(n) and g(n) as given below. Use the most precise asymptotic notation to show how function f is related to function g in each case ( i. e. , f ∈ ?(g)). For example, if you were given the pair of functions f (n) = n and g(n) = n2 then the correct answer would be: f ∈ o(g). To avoid any ambiguity between O(g) and o(g) notations due to writing, use Big-O(g) instead of O(g).

1.

The relation is: f = Θ(g)

For c1 = 1 and c2 = 200, and n >= 0, we have

0 <= g(n) <= f(n) <= 200*g(n)

Hence, f = Θ(g)

2.

The relation is: f = Ω(g)

For very large values of n,

0 <= g(n) <= f(n)

Hence, f = Ω(g)

3.

The relation is: f = Ω(g)

Since, for n >= 0,

log2n > log3n

Hence, f = Ω(g)

4.

The relation is: f = Big-O(g)

For all n >= 0,

2n <= 3n

Hence, f = Big-O(g)

5.

The relation is: f = Big-O(g)

For n >= 0,

0.5n < 1

Hence, f = Big-O(g)

Explanation: