Discrete Mathematics for Computer Science

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 > No.


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^30 O(n^2 + 5n + 3).