Use a recursion tree to determine a good asymptotic upper bound on the recurrence \(T(n) = 3T(\lfloor n/2 \rfloor) + n\). Use the substitution method to verify your answer.
The recurrence \(T(n) = 3T(\lfloor n/2 \rfloor) + n\) has the following recursion tree:
Adding up the costs of each level of the tree:
\[\begin{split} T(n) & = n + \frac{3}{2}n + \left(\frac{3}{2}\right)^2 n + \cdots + \Theta(n^{\lg 3}) \\ & = \sum\limits_{i=0}^{\lg(n-1)} \left(\frac{3}{2}\right)^i n + \Theta(n^{\lg 3}) \\ & < \sum\limits_{i=0}^{\infty} \left(\frac{3}{2}\right)^i n + \Theta(n^{\lg 3}) \\ & = \frac{1}{1-\frac{3}{2}}n + \Theta(n^{\lg 3}) \\ & = -2n + \Theta(n^{\lg 3}) \\ & = O(n^{\lg 3}) \\ \end{split}\]Based on this calculation, we guess that \(T(n) \leq cn^{\lg 3} - bn\). Substituting this into the recurrence yields
\[\begin{split} T(n) & \leq 3(c(\lfloor n/2 \rfloor)^{\lg 3} - b(n/2)) + n \\ & = \left(\frac{3}{2}\right)^{\lg 3} cn^{\lg 3} - \frac{3bn}{2} + n \\ & = cn^{\lg 3} + \left(1 - \frac{3b}{2} \right)n \\ & \leq cn^{\lg 3} - bn \\ \end{split}\]Where the last step holds for \(b \geq 2\).
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.5\linewidth}
\centering
\begin{tikzpicture}[scale=.85,sibling distance=0pt]
\Tree [.$n$
[.$\frac{n}{2}$
[.$\frac{n}{4}$
[.$\vdots$
[.$T(1)$ ] ] ]
[.$\frac{n}{4}$
[.$\vdots$
[.$T(1)$ ] ] ]
[.$\frac{n}{4}$
[.$\vdots$
[.$T(1)$ ] ] ] ]
[.$\frac{n}{2}$
[.$\frac{n}{4}$
[.$\vdots$
[.$T(1)$ ] ] ]
[.$\frac{n}{4}$
[.$\vdots$
[.$T(1)$ ] ] ]
[.$\frac{n}{4}$
[.$\vdots$
[.$T(1)$ ] ] ] ]
[.$\frac{n}{2}$
[.$\frac{n}{4}$
[.$\vdots$
[.$T(1)$ ] ] ]
[.$\frac{n}{4}$
[.$\vdots$
[.$T(1)$ ] ] ]
[.$\frac{n}{4}$
[.$\vdots$
[.$T(1)$ ] ] ] ] ]
\end{tikzpicture}
\end{minipage}
\begin{minipage}[b]{0.4\linewidth}
\centering
\begin{tikzpicture}[scale=.85,sibling distance=0pt]
\Tree [.$n$
[.$\frac{3}{2}n$
[.$\frac{9}{4}n$
[.$\vdots$
[.$\Theta(n^{\lg3})$ ] ] ] ] ]
\end{tikzpicture}
\end{minipage}
\end{figure}
\end{document}