Exercise 4.3.8

Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n/2) + n^2$ is $T(n) = \Theta(n^2)$. Show that a substitution proof with the assumption $T(n) \leq cn^2$ fails. Then show how to subtract off a lower-order term to make the substitution proof work.

Well:

$$ T(n) \le 4c(n/2)^2 + n^2 \leq cn^2 + n^2 \leq (c + 1)n^2 $$

Dead-end!

Now we guess $T(n) \le cn^2 - n$:

$$ \begin{aligned} T(n) & \le 4\Big(c(n/2)^2 - n/2\Big) + n \\ & \le cn^2 - 2n + n \\ & \le cn^2 - n \end{aligned} $$