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.

#### Recursion Tree

Rate of increase in number of subproblems in each recursion = 1

Rate of decrease in subproblem size = 2

Hence at depth $$i = 0, 1, 2, \dots, \lg n$$ of the tree, there is only one node of cost $$(n/2^i)^2$$.

Hence, total cost of the tree is:

\begin {aligned} T(n) & = \sum_{i = 0}^{\lg n} \left(\frac n {2^i}\right)^2 \\ & = n^2 \cdot \sum_{i = 0}^{\lg n} \left(\frac 1 4\right)^i \\ & \le n^2 \cdot \sum_{i = 0}^{\infty} \left(\frac 1 4\right)^i \\ & = O(n^2) \end {aligned}

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

#### Verification Using Substitution

Let’s assume, $$T(n) \le cn^2$$, for all $$n \ge n_0$$, where $$c$$ and $$n_0$$ are some positive constants.

\begin {aligned} T(n) & = T(n/2) + n^2 \\ & \le c(n/2)^2 + n^2 \\ & = c n^2/4 + n^2 \\ & = (c/4 + 1) n^2 \\ & \le cn^2 \end {aligned}

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