Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = T(n/2) + n^2$. 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 $c(n/2^i)^2$ at depth $i = 0, 1, 2, \dots, \lg n$.

Hence, total cost of the tree is:

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

Now we have to show that our guess $T(n) = O(n^2)$ holds using the substitution method.

The last step holds as long as $d \ge d/4 + 1$, i.e. $d \ge 4/3$.