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.

#### Recursion Tree

Rate of increase in number of subproblems in each recursion = 2

Rate of decrease in subproblem size = 1 with 1 less input

Hence at depth $$i = 0, 1, 2, \dots, n$$ of the tree, there are $$2^i$$ nodes each of cost $$1$$.

Hence, total cost of the tree is:

\begin {aligned} T(n) & = \sum_{i = 0}^{n} 2^i \cdot 1 \\ & = \frac {2^{n + 1} - 1} {2 - 1} \\ & = 2^{n + 1} - 1 \\ & = 2.2^n - 1 \\ & \le c2^n \\ & = O(2^n) \end {aligned}

The last step holds as long as $$c \ge 2$$ and $$n \ge 1$$.

#### Verification Using Substitution

Let’s assume, $$T(n) \le c2^n$$, for all $$n \ge n_0$$, where $$c$$ and $$n_0$$ are some positive constants.

\begin {aligned} T(n) & = 2T(n - 1) + 1 \\ & \le 2c 2^{n - 1} + 1 \\ & = c2^n + 1 \end {aligned}

We cannot prove our assumption from above. Let’s modify our initial assumption by subtracting a lower-order term, $$T(n) \le c2^n - b$$, for all $$n \ge n_0$$, where $$c$$, $$b$$, and $$n_0$$ are some positive constants.

\begin {aligned} T(n) & = 2T(n - 1) + 1 \\ & \le 2 \cdot (c2^{n - 1} - b) + 1 \\ & = c2^n - 2b + 1 \\ & = c2^n - b - (b - 1) \\ & \le c2^n - b \end {aligned}

The last step holds as long as $$b \ge 1$$.