PS16: Asymptotics & Running-Time Analysis

Due Wed 10/29 @ 10am.

Do these problems from the book, listed on page 613 & 614.

  1. 6.2
  2. 6.3
  3. 6.4
  4. 6.18
  5. 6.27
  6. 6.53, which contains a typo: the label on the base case should be “(n=0)”.

Also do these problems, listed on page 628.

  1. 6.72
  2. 6.73 (note that a c,N-style argument is not necessary here)
  3. 6.74

Also do these problems, listed on pages 649 & 650.

  1. 6.82
  2. 6.83
  3. 6.84
  4. 6.85
  5. 6.86 (Do this one just for bar, but write your proof without using the Master Theorem.)
  6. 6.89
  7. 6.91