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\).