CS 241, Fall 99, Homework 2 Practice Exercises

Homework 2 follows up on a lot of problems done in Homework 1. Thus you should also use Homework 1 and the HW 1 practice problems for this purpose.

If you are having problems with solving the recurrence for Algorithm E of problem 2, look over the solution from Challenge Problem 1 from HW 1. They are very similar problems. If you any questions about how this solutions was derived please come to our office hours and we'll guide you throught it. (It may help if you draw the recurrence tree.)

If you would like additional practice problems, please let me know which type of problems you want more practice with.

1. Give tight asymptotic bounds for T(n) in each of the following recurrences. Assume that T(1)=1. (Hint: Use the master method.)
   • (a) T(n) = 9T(n/9) + Theta(n)

     solution

   • (b) T(n) = 9T(n/9) + Theta(1)

     solution

   • (c) T(n) = 9T(n/9) + Theta(n^2)

     solution

   • (d) T(n) = T(9n/10) + Theta(1)

     solution

   • (e) T(n) = 8T(n/2) + Theta(n^3 log n)

     solution

2. Give an asymptotically tight solution to the recurrence

   T(n) = T(n-2) + 3n
   T(0) = c
   

   solution