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}\]