Use a recursion tree to determine a good asymptotic upper bound on the recurrence \(T(n) = 2T(n-1) + 1\). Use the substitution method to verify your answer.
The recurrence \(T(n) = 2T(n-1) + 1\) has the following recursion tree:
Adding up the costs of each level of the tree:
\[\begin{split} T(n) & = 1 + 2 + 4 + 8 + \cdots + \Theta(2^n) \\ & = \sum\limits_{i=0}^{n-1} 2^i + \Theta(2^n) \\ & = \frac{2^n - 1}{2 - 1} + \Theta(2^n) \\ & = 2^n - 1 + \Theta(2^n) \\ & = O(2^n) \\ \end{split}\]Based on this calculation, we guess that \(T(n) \leq 2^n\). Substituting this into the recurrence yields
\[\begin{split} T(n) & \leq 2c(2^{n -1}) + 1 \\ & = c(2^n) + 1 \\ & \leq c(2^n) \end{split}\]which does not hold. We can fix this quickly by modifying our original guess with a subtracted constant so that we can deal with that pesky \(1\). Substituting our new guess of \(T(n) \leq 2^n - b\) into the recurrence yields
\[\begin{split} T(n) & \leq 2c(2^{n -1} - b) + 1 \\ & = c(2^n) + 1 - b \\ & \leq c(2^n) \end{split}\]Where the last step holds for \(b \geq 1\).
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=.75,sibling distance=0pt]
\Tree [.$1$
[.$1$
[.$1$
[.$1$
[.$\vdots$
[.$\Theta(1)$ ] ] ]
[.$1$
[.$\vdots$
[.$\Theta(1)$ ] ] ] ]
[.$1$
[.$1$
[.$\vdots$
[.$\Theta(1)$ ] ] ]
[.$1$
[.$\vdots$
[.$\Theta(1)$ ] ] ] ] ]
[.$1$
[.$1$
[.$1$
[.$\vdots$
[.$\Theta(1)$ ] ] ]
[.$1$
[.$\vdots$
[.$\Theta(1)$ ] ] ] ]
[.$1$
[.$1$
[.$\vdots$
[.$\Theta(1)$ ] ] ]
[.$1$
[.$\vdots$
[.$\Theta(1)$ ] ] ] ] ] ]
\end{tikzpicture}
\end{minipage}
\begin{minipage}[b]{.2\linewidth}
\centering
\begin{tikzpicture}[scale=.75,sibling distance=0pt]
\Tree [.$1$
[.$2$
[.$4$
[.$8$
[.$\vdots$
[.$\Theta(2^n)$ ] ] ] ] ] ]
\end{tikzpicture}
\end{minipage}
\end{figure}
\end{document}