Question

6. (15) Determine whether each statement is true or false. Justify your answers.
(a) if f(n) = O(g(n)), then g(n) = O(f(n)).

(b) if f(n) = O(g(n)), then g(n) = Ω(f(n)).

(c) if f(n) = Θ(g(n)), then g(n) = Θ(f(n)).

Answer 1

a)False, this cannot be true because in BIg-oh notation The function inside the O() are asymptotically greater than the function that is present outside.So Both cannot be possible at the same time.

b) f(n) =O(g(n)) means the rate of growth of g(n) is larger than f(n) or g(n) is asymptotically has larger order than f(n).

And g(n)=omega(f(n)) means f(n) is smaller than g(n) so both have the same meaning.

So this is true.

c) In omega notation,the function inside omega() is asymptotically equal to the function present at outside i.e. both have same rate of growth so this can be written at either way.So this is True.