If f(n) is O(g(n)) and f(n) is O(h(n)), then which of the following statements MUST be true:

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

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

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

D. None of the above

1 Like

A must be true…

because if f(n) is O(g(n)) then f(n) < cg(n) for sufficiently large n and similarly for f(n) and h(n)

C is true; both A and B are false.

To see that A and B are false, take f=n, g=n^3, h=n^2.

1 Like