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.

Rate of increase in number of subproblems in each recursion = 2 Rate of decrease in subproblem size = 1 with 1 less input

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

Hence, total cost of the tree is:

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

Now we have to show that our guess $T(n) = O(2^n)$ holds using the substitution method. Let’s refine our guess to $T(n) \le d(2^n - b)$ for positive constants $b$ and $d$.

The last step holds as long as $db - 1 \ge 0$.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.