Gate Practice Question

Question

for n>=0 , if f(n)<g(n) and h(n)<g(n) . How many of the following are false. ?

1. f(n) is O(h(n)).

2.f(n) is not O(g(n)).

3.f(n)+h(n) is O(g(n)).

4.g(n) is not O(f(n)).

5.f(n)*h(n) is O(g(n)).

Answer 1

the answer should be 3 

1) f(n) is O(h(n)) is false as there is no comparision given  between f(n) and h(n).

2) f(n) is not  O(g(n)) is also false as f(n) < g(n) it is O(g(n)).

3) f(n) + g(n) will be max( f(n), g(n) ) which will in turn be O(g(n)).

4) g(n) is not O(f(n)) is also true as f(n)< g(n).

5) f(n)*h(n) may be O(g(n)) in some cases but not always hence  it is false too.