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 = 1 Rate of decrease in subproblem size = 2

Hence in each level of the tree, there is only one node of cost at depth .

Hence, total cost of the tree is:

The last step comes from the fact that the sum is independent of , resulting in a constant factor.

Now we have to show that our guess holds using the substitution method.

The last step holds as long as , i.e. .

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