Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = T(n - 1) + T(n/2) + n$. Use the substitution method to verify your answer.

There are two subproblems at each step,

1. One with input size one less than previous step
2. 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 $c(n - i)$ at depth $i = 0, 1, 2, \dots, n$.

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 $cn/2^i$ at depth $i = 0, 1, 2, \dots, \lg n$.

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 $O(n^2)$.

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.