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

a. $T(n) = 2T(n/2) + n^4$.

$a = 2$, $b = 2$ and $f(n) = n^4$.

Case 1 does not apply since $f(n) = O(n^{\log_{2}2 - \epsilon}) \implies \epsilon = -3$.

Case 2 does not apply since $f(n) \neq \Theta(n^{\log_{2} 2})$.

Case 3 applies since $f(n) = \Omega(n^{\log_{2}2 + \epsilon}) = \Omega(n^{1 + 3})$ and

$$\begin{split} a(f(n/b)) & \leq cf(n) \\ 2\left(\frac{n}{2}\right)^4 & \leq cn^4 \\ \frac{n^4}{8} & \leq cn^4 \\ \end{split}$$

holds for $\frac{1}{8} \leq c \leq 1$. Thus the solution to the recurrence is $T(n) = \Theta(f(n)) = \Theta(n^4)$.

b. $T(n) = T(7n/10) + n$.

$a = 1$, $b = \frac{10}{7}$ and $f(n) = n$.

Case 1 does not apply since $f(n) = O(n^{\log_{10/7} 1 - \epsilon}) = O(n^{0 - \epsilon}) \implies \epsilon = -1$.

Case 2 does not apply since $f(n) \neq \Theta(n^{\log_{10/7} 1})$.

Case 3 applies since $f(n) = \Omega(n^{\log_{10/7}1 + \epsilon}) = \Omega(n^{0+1})$ and

$$\begin{split} af(n/b)) & \leq cf(n) \\ \frac{7n}{10} \cdot \frac{7}{10} & \leq \frac{7cn}{10} \\ \frac{49n}{100} & \leq \frac{7cn}{10} \\ \frac{49n}{70} & \leq cn \\ \end{split}$$

holds for $\frac{49}{70} \leq c < 1$. Thus the solution to the recurrence is $T(n) = \Theta(f(n)) = \Theta(n)$.

c. $T(n) = 16T(n/4) + n^2$.

$a = 16$, $b = 4$ and $f(n) = n^2$.

Case 1 does not apply since $f(n) = O(n^{\log_{4} 16 - \epsilon}) = O(n^{2 - \epsilon}) \implies \epsilon = 0$.

Case 2 applies since $f(n) = \Theta(n^{\log_{4} 16}) = \Theta(n^2)$. Thus the solution to the recurrence is $T(n) = \Theta(n^{\log_{4} 16} \lg n) = \Theta(n^2 \lg n)$.

d. $T(n) = 7T(n/3) + n^2$.

$a = 7$, $b = 3$ and $f(n) = n^2$.

Case 1 does not apply since $f(n) = O(n^{\log_{3} 7 - \epsilon}) \implies \epsilon < 0$.

Case 2 does not apply since $f(n) \neq \Theta(n^{\log_{3} 7})$.

Case 3 applies since $f(n) = \Omega(n^{\log_{3} 7 + \epsilon}) \approx \Omega(n^{1.77 + .23})$ and

$$\begin{split} a(f(n/b)) & \leq cf(n) \\ 7 \left(\frac{n}{3}\right)^2 & \leq cn^2 \\ \frac{7n^2}{9} & \leq cn^2 \\ \end{split}$$

holds for $\frac{7}{9} \leq c < 1$. Thus the solution to the recurrence is $T(n) = \Theta(f(n)) = \Theta(n^2)$.

e. $T(n) = 7T(n/2) + n^2$.

$a = 7$, $b = 2$ and $f(n) = n^2$.

Case 1 applies since $f(n) = O(n^{\log_{2}7 - \epsilon}) \approx O(n^{2.8 - 0.8})$. Thus the solution to the recurrence is $T(n) = \Theta(n^{\log_{b} a}) = \Theta(n^{\lg 7})$.

f. $T(n) = 2T(n/4) + \sqrt{n}$.

$a = 2$, $b = 4$ and $f(n) = \sqrt{n}$.

Case 1 does not apply since $f(n) = O(n^{\log_{4} 2 - \epsilon}) \implies \epsilon = 0$.

Case 2 applies since $f(n) = \Theta(n^{\log_{4} 2}) = \Theta(n^{0.5})$. Thus the solution to the recurrence is $T(n) = \Theta(n^{\log_{4} 2} \lg n) = \Theta(\sqrt{n} \lg n)$.

g. $T(n) = T(n-2) + n^2$.

This recurrence has a height of $\frac{n}{2}$ and adding up the costs for each level of the ‘tree’:

$$\begin{split} T(n) & = cn^2 + c(n-2)^2 + c(n-4)^2 + \cdots \\ & = c \sum\limits_{i=0}^{n/2} (n-2i)^2 \\ & = c \sum\limits_{i=0}^{n/2} (n^2 - 4ni + 4i^2) \\ & = c \left( \sum\limits_{i=0}^{n/2} n^2 - \sum\limits_{i=0}^{n/2} 4ni +\sum\limits_{i=0}^{n/2} 4i^2 \right) \\ & = \Theta(n^3) - \Theta(n^2) + \Theta(n^3) \\ & = \Theta(n^3) \\ \end{split}$$