Use a recursion tree to determine a good asymptotic upper bound on the recurrence \(T(n) = T(n/2) + n^2\). Use the substitution method to verify your answer.
The recurrence \(T(n) = T(n/2) + n^2\) has the following recursion tree (Note that the left side is the tree itself and the right side is the ‘sum’ of that level):
Adding up the costs of each level of the tree:
\[\begin{split} T(n) & = n^2 + \left(\frac{1}{4}\right)n^2 + \left(\frac{1}{16}\right)n^2 + \cdots + \Theta(1) \\ & = \sum\limits_{i=0}^{\lg(n-1)} \left(\frac{1}{4}\right)^i n^2 + \Theta(1) \\ & < \sum\limits_{i=0}^{\infty} \left(\frac{1}{4}\right)^i n^2 + \Theta(1) \\ & = \frac{1}{1 - \frac{1}{4}}n^2 + \Theta(1) \\ & = \Theta(n^2) \\ \end{split}\]Based on this calculation, we guess that \(T(n) \leq cn^2\). Substituting this into the recurrence yields
\[\begin{split} T(n) & \leq c\left(\frac{n}{2}\right)^2 + n^2 \\ & = \frac{cn^2}{4} + n^2 \\ & = n^2\left(\frac{c}{4} + 1\right) \\ & \leq cn^2 \end{split}\]Where the last step holds for \(c \geq \frac{3}{4}\).
The following LaTeX code was used to generate the above recursion tree:
\documentclass[12pt]{article}
\usepackage{forest}
\usepackage{tikz-qtree}
\begin{document}
\begin{figure}
\begin{minipage}[b]{0.3\linewidth}
\centering
\begin{tikzpicture}[scale=1,sibling distance=0pt]
\Tree [.$n^2$
[.$(n/2)^2$
[.$(n/4)^2$
[.$\vdots$
[.$\Theta(1)$ ] ] ] ] ]
\end{tikzpicture}
\end{minipage}
\begin{minipage}[b]{0.1\linewidth}
\centering
\begin{tikzpicture}[scale=1,sibling distance=0pt]
\Tree [.$n^2$
[.$(1/4)n^2$
[.$(1/16)n^2$
[.$\vdots$
[.$\Theta(1)$ ] ] ] ] ] ]
\end{tikzpicture}
\end{minipage}
\end{figure}
\end{document}