Exercises
297
14. Show that:
(a) sin(n) E 0(1)-that is, the sine function is asymptotically dominated by the constant function 1.
(b) n sin(n) e O(n).
15. Prove that f/i E O(n) and that n 0 O(V'n-).
16. Prove or find a counterexample. If O(G) = O(F) and O(H) C O(F), then for all but
finitely many n E N, H(n) < G(n).
17. Prove that ln(n) E O(n) but that n O O(ln(n)) for n E N.
18. Prove that n
3 E 0(n') and that n' € O(n
3 ).
19. Prove that for all b, c > 1, O(logb) = O(logc).
20. Complete the proof of Corollary 2 to Theorem 3.
21. Prove Theorem 4.
22. Prove Theorem 5.
23. Prove Theorem 8.
24. Finish the proof of Theorem 6. For a polynomial function
P(n) = ak nk + ak-1 nk-1 +
+ a2 n2 + al n + ao
where ak > 0 and for
No= 2 Flak-l I + Iak-2E +'
+ jai I + lao 1+2
I
ak
prove that for all n > No,
ak nk/2 < P(n) < 3ak nk/2
25. Consider a polynomial
P(n) = ak nk + ak-l nk-1 +
+ a2 n2 + al n + aO
as a function from IR to IR. Show how to compute a number N so that all roots of
P(n) = 0 occur between -N and N. Prove that your answer is correct.
26. For functions F, G : N -+ (0, oo), F is said to be in o(G) if
F(x)
lim
--0
x--o G(x)
(a) Show that if F E o(G), then F E O(G) and G 0 O(F).
(b) Use this result to give an alternative proof of Theorem 5.
27. For functions F, G : N -- (0, co), F is said to be in 0(G) if
lim F(x)
x-oo G(x)
for some c E (0, c0).
(a) Show that if F E O(G), then O(G) = O(F).
(b) Use this result to give an alternative proof of Theorem 6.