Computer Science 3650
Summer 2000
Exercise 2

1. (page 64, 4-3-1) Use the master method to give tight asymptotic bounds for each of the following recurrences.
   1. T(n) = 4T(n/2) + n
   2. T(n) = 4T(n/2) + n²
   3. T(n) = 4T(n/2) + n³

2. (page 64, 4-3-2) The running time of algorithm A is described by the recurrence T(n) = 7T(n/2) + n². A competing algorithm A' has a running time of T'(n) = aT(n/4) + n². What is the largest integer value for a such that A' is asymptotically faster than A?

3. (page 72, 4-1 a-c) Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n <= 2. Make your bounds as tight as possible, and justify your answers.
   1. T(n) = 2T(n/2) + n³
   2. T(n) = T(9n/10) + n
   3. T(n) = 16T(n/4) + n²