Description
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
