Use a recursion tree to determine a good asymptotic upper bound on the recurrence . 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 nodes each of cost at depth .
Hence, total cost of the tree is:
The last step holds as long as and .
Now we have to show that our guess holds using the substitution method. Let’s refine our guess to for positive constants and .
The last step holds as long as .