##### GATE 2004 Example on Complexity Analysis

Let $f(n)$, $g(n)$ and $h(n)$ be functions defined for positive integer such that $f(n) = O(g(n))$, $g(n) \neq O(\ f(n) \ )$, $g(n) = O(\ h(n) \ )$, and $h(n) = O(\ g(n) \ )$.

Which one of the following statements is FALSE ?

A) f(n) + g(n) = O( h(n) ) + h(n)
B) f(n) = O( h(n) )
C) h(n) ≠ O( f(n) )
D) f( n )h( n ) ≠ O( g(n)h(n) )

$\because f(n) = O(g(n)) \ \ and \ \ g(n) = O(h(n)) \\ \therefore f(n) = O(h(n)) \\ \implies (B) \ \ is \ \ TRUE \ \ and \ \ (C) \ \ is \ \ TRUE$

and,

$\because g(n) = O(h(n)) \ \ and \ \ h(n) = O(g(n)) \\ \therefore g(n) = h(n) \\ \implies (A) \ \ is \ \ TRUE \ \ But \ \ (D) \ \ is \ \ FALSE$

∴ Ans (D)