Description
1. First use the iteration method to solve the recurrence, draw the recursion tree to analyze.
T(n) = T(
n
2
) + 2T(
n
8
) + n
2
Then use the substitution method to verify your solution.
2. Use the substitution method to prove that,
T(n) = 2T(
n
2
) + cn log n
is O(n(log n)
2
), where c > 0 is a constant. (log ≡ log2
, in this and the following questions)
3. Solve the recurrence:
T(n) = 2T(
√
n) + (log log n)
2
(Hint: How to make change of variables so that you can apply Master’s method?)
4. You want to solve the following three recurrence formulas:
A: T(n) = 5T(
n
2
) + an
B: T(n) = T(
n
3
) + bn2
C: T(n) = 3T(
n
3
) + cn log n
Can you use Master’s method for each of these? If yes, write down how you check the conditions and
the answer. If not, briefly explain why and solve using other methods.
(Hint: You may need the harmonic series, i.e. when n is very large, log n ≈
Pn
k=1
1
k
)
1