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\).