# Problem 4.1

## Recurrence examples

Give asymptotic upper and lower bound for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for $n \le 2$. Make your bounds as tight as possible, and justify your answers.

1. $T(n) = 2T(n/2) + n^4$
2. $T(n) = T(7n/10) + n$
3. $T(n) = 16T(n/4) + n^2$
4. $T(n) = 7T(n/3) + n^2$
5. $T(n) = 7T(n/2) + n^2$
6. $T(n) = 2T(n/4) + \sqrt{n}$
7. $T(n) = T(n - 2) + n^2$
1. $\Theta(n^4)$ (master method)
2. $\Theta(n)$ (master method, $\log_{10/7}1 = 0$)
3. $\Theta(n^2\lg{n})$ (master method)
4. $\Theta(n^2)$ (master method)
5. $\Theta(n^{\log_2{7}})$ (master method)
6. $\Theta(\sqrt{n}\lg_{n})$ (master method)
7. $T(n) = n^2 + T(n - 2) = n^2 + (n - 2)^2 + T(n - 4) = \sum_{i=0}^{n/2}(n -2i)^2 = \Theta(n^3)$