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