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)