Exercises 297
- Show that:
(a) sin(n) E 0(1)-that is, the sine function is asymptotically dominated by the con-
stant function 1.
(b) n sin(n) e O(n).
- Prove that f/i E O(n) and that n 0 O(V'n-).
- 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).
- Prove that ln(n) E O(n) but that n O O(ln(n)) for n E N.
- Prove that n^3 E 0(n') and that n' € O(n^3 ).
- Prove that for all b, c > 1, O(logb) = O(logc).
- Complete the proof of Corollary 2 to Theorem 3.
- Prove Theorem 4.
- Prove Theorem 5.
- Prove Theorem 8.
- 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
- 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.
- 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.
