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. $\Theta(n^3)$ by the following:

$$ \begin{aligned} T(n) &= n^2 + T(n - 2) \\ &= n^2 + (n - 2)^2 + T(n - 4) \\ &= \sum_{i=0}^{n/2}(n -2i)^2 \\ &= n^2 \sum_{i=0}^{n/2} 1 + 4 \sum_{i=0}^{n/2} i^2 - 4n \sum_{i=0}^{n/2} i \\ \end{aligned}$$

For the three sums above:

$$n^2 \sum_{i=0}^{n/2} 1 = \frac{n^3}{2}$$

$$4 \sum_{i=0}^{n/2} i^2 = \frac{4}{6} \left[\frac{n}{2}\left(\frac{n+2}{2}(n+1)\right)\right] = \frac{1}{3}(2n^3 + 6n^2 + 4n)$$

$$4n \sum_{i=0}^{n/2} i = 4n\left[\frac{1}{2}\frac{n}{2}\left(\frac{n+2}{2}\right)\right] = \frac{1}{2}(n^3 + 2n^2)$$

Now substitute back in these 3 simplifications:

$$ \begin{aligned} T(n) &= n^2 \sum_{i=0}^{n/2} 1 + 4 \sum_{i=0}^{n/2} i^2 - 4n \sum_{i=0}^{n/2} i \\ &= \frac{n^3}{2} + \frac{1}{3}(2n^3 + 6n^2 + 4n) - \frac{1}{2}(n^3 + 2n^2) \\ &= \frac{2}{3}n^3 + n^2 + \frac{4}{3}n \\ &= \Theta(n^3) \end{aligned}$$