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

 

Answer

\(\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)

 

 

 

 

 

2Comments
Shubh @shubhammeshr
8 Oct 2017 10:38 am

how it option d plz explain

shivani @shivani1234
9 Oct 2017 02:56 pm

 f(n)=O(g(n)), g(n)≠O( f(n) ), g(n)=O( h(n) ), and h(n)=O( g(n) ).
it means f < g and g=h that means f < h
f( n )h( n ) ≠ O( g(n)h(n) ) is false since ,  f(n)=O(g(n))