Consider the recurrence $T(n)=2T(n-1)+1.$

a$.$ Part A $[1$ pts$]$: Draw the top three levels of the recursion tree for this example, as

was shown in the in$-$class exercise. Be sure to list the total amount of work done at

each level. ${?}^1$

Solution:

b$.$ Part B $[1$ pts$]$: Guess a big$-$O upper bound for the running time of this recurrence.

Explain your answer in a sentence or two.

Solution:

c$.$ Part C $[1$ pts$]$: Use substitution to prove your guess for the upper bound.

Solution:

Thank you!