Use a recursion tree to determine a good asymptotic upper bound on the recurrence . Use the substitution method to verify your answer.

There are two subproblems at each step,

- One with input size one less than previous step
- Another with input size half of the previous step

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

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

Hence, total cost of the tree is:

**Subproblem #2**
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 one node of cost at depth .

Hence, total cost of the tree is:

So, sub-problem #1 is computationally more intensive than sub-problem #2. Hence, our guess for the solution of the recurrence is .

We can easily prove this guess is righ using substitution method as in earlier exercises. We might need to add/subtract a smaller term from the guess.