Module 4 Problems
In the problems below, you must justify your answer, not just state it.
Find the tightest asymptotic complexity for the following recurrences.
Give your answer in Big Oh notation.
(Justify your answer)
1. [4 pts] T(n) = 3 T(n/2) + n^2
2. [4 pts] T(n) = 4 T(n/2) + n^2
3. [4 pts] T(n) = T(n/2) + n^2
4. [4 pts] T(n) = 16 T(n/4) + n
5. [4 pts] T(n) = 2 T(n/2) + n log(n)
6. [4 pts] T(n) = 2 T(n/2) + n/log(n)
7. [4 pts] T(n) = 2 T(n/4) + n^(0.51)
8. [4 pts] T(n) = 6 T(n/3) + n^2 log(n)
9. [4 pts] T(n) = 7 T(n/3) + n^2
10. [4 pts] T(n) = sqrt(2) T(n/2) + log(n)
For the next 2 problems, give the -full- solution for the recurrence, -notjust the Big Oh solution. Please note that your solution must solve
all of the special cases, as well as the general recurrence.
Hint: Consider the method of undetermined coefficients.
11. [8 pts] Solve the recurrence
T(n) = 3T(n/3) + 1
T(1) = 2
12. [12 pts] Solve the recurrence
T(n) = nT(n-1)
T(2) = 150
13. [15 pts] For the following recurrence, give a tight Big Oh bound
for the asymptotic complexity of the recurrence.
Hint: Consider recursive substitution.
Solve the recurrence
T(n) = T(9n/10) + T(n/10) + n
14. [25 pts] Find the asymptotic complexity of the following recurrence. Give a
proof
sketch showing that your asymptotic is correct. In the recurrence,
assume that 0 < a < 1.
Hint: This recurrence generalizes problem 13.
Find a tight Big Oh complexity for this recurrence:
T(n) = T(an) + T((1-a)n) + n
