296
CHAPTER 5 Analysis of Algorithms
U Exercises
1. Find a real number c and an No E N such that n
2 + 5n < cn
2 for all n E N with
n > No.
2. Find a real number c and an No E N such that n
3 + 5n
2 + 2n < cn
3 for all n E N with
n > No.
3. Find a real number c and an No E N such that n
2 ± 3n < cn
3 for all n E N with
n > N o .
4. Find a real number c and an No E N such that n
3 - 3n
2 + 4n < cn
3 for all n e N with
n > No.
5. (a) Find a real number c and an No E N such that n
2 < cn
3 for all n E N with n > No.
(b) Find a real number c and an No E N such that 5n < cn
3 for all n E N with n > No.
6. Using the proof of the Corollary 1 to Theorem 1 as a model, find a real number c and
an No E N such that 5n
3 E O(n
3 ) for all n c N with n > No.
7. Using the proof of the Corollary I to Theorem 1 as a model, find a real number c and
an No c N such that 7n
4 E O(n
4 ) for all n e N with n > No.
8. (a) Find a real number c and an No • N such that n
2 - 3n E O(n
3 ).
(b) Find a real number c and an No e N such that 2n
2 + 7n e O(n
3 ).
(c) Using part (a), part (b), and Theorem 3, prove that 3n
2 + 4n E O(n
3 ).
(d) Using part (a), part (b), and Theorem 3, prove that In2 - In I O(n
3 ).
(e) Using part (a), part (b), and Theorem 3, prove that 5(n
2 - 3n) + 6(2n
2 + 7n) E
O(n3).
9. (a) Find a real number c and an No E N such that 2n
2 + 7n E O(n
3 ).
(b) Find a real number c and an No E N such that 3n
2 - 7n E O(n
3 ).
(c) Using part (a), part (b), and Theorem 3, find c and No to prove that 5n
2 E O(n
3 ).
(d) Using part (a), part (b), and Theorem 3, find a real number c and an No E N to
prove that I n
2 - 14n I E O(n
3 ).
(e) Using part (a), part (b), and Theorem 3, find a real number c and an No G N to
prove that 5(2n
2 + 7n) + 3(3n
2 - 7n) E O(n
3 ).
10. (a) Find a real number c and an No E N such that n
2 + 3n E O(n
3 ).
(b) Find a real number c and an No E N such that 3n
3 E O(n
4 ).
(c) Using part (a), part (b), and Theorem 2, find c and No to prove that n
2 + 3n E
O(n4).
11. (a) Find a real number c and an No E N such that 2n
2 - 5n e O(n
3 + 5n
2 ).
(b) Find a real number c and an No E N such that 6n
3 + 5n
2 E O(n
4 ).
(c) Using part (a), part (b), and Theorem 2, find c and No to prove that 2n
2 - 5n E
O(n4).
12. Using the proof of Theorem 6 as a guide:
(a) Find a real number c and an No E N such that n
2 - 3n E 0(n
3 ).
(b) Show that n
3 0 O(n
2 - 3n).
13. Using the proof of Theorem 6 as a guide:
(a) Find a real number c and an No E N such that n
2 + 5n + 3 E O(n
3 ).
(b) Show that n
3 0 O(n
2 + 5n + 3).