Description
(5 pts.) (a) Determine a good asymptotic upper bound on the recurrence T(n) = 5T(⌊n/3⌋) + n
by the iteration method.
(5 pts.) (b) Draw the recursion tree to determine a good asymptotic upper bound on the recurrence
T(n) = 3T (⌊n/2⌋) + 9n. Verify your bound by the substitution method.
(5 pts.) (c) Draw the recursion tree for the recurrence T(n) = 3T
n/√
3
+ cn, where c is a
constant, and determine a good asymptotic upper bound on its solution. Verify your
bound by the substitution method.
(5 pts.) (d) Using the substitution method, show that the solution to T(n) = 2T(⌊n/2⌋ + 13) + 2n
is O(n log n).
(6 pts.) (e) Use the master method to give tight asymptotic bounds for the following recurrence
relations:
2 pts. (1) T(n) = 32T(n/6) + 5n.
2 pts. (2) T(n) = 36T(n/6) + 5n
2 + 4n.
2 pts. (3) T(n) = 42T(n/6) + 25n
3 + 5n
2 + n.
(5 pts.) (f) The recurrence T(n) = 8T(n/2) + 2n
2 describes the running time of algorithm 1.
Algorithm 2, has a running time of T(n) = aT(n/4) + n
2
, where a is a constant. What
is the largest integer value for a such that algorithm 2 is asymptotically faster than
algorithm 1.
(10 pts.) (g) Give tight bounds for the solution to the following recurrence relations. Use any
rigorous method you wish. Justify your answers. Show all work. Explicitly state any
assumptions you make.
1. T(n) = 42T(n/42) + n
3
.
2. T(n) = 36T(n/6) + n
2
.
3. T(n) = 7T(n/2) + n
2.333
.
4. T(n) = 2T(n/16) + √4 n.
5. T(n) = T(n − 2) + 3n + 1.