Use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound
Let's assume that $n$ is a power of 2 (otherwise the recurrence isn't really defined all the way), with a base case at $n=1$. Then
$$
\begin{align*}
T(n) &amp;= n^2 + 4T(n/2) \\ &amp;=
n^2 + 4(n/2)^2 + 16T(n/4) \\ &amp;=
n^2 + 4(n/2)^2 + 16(n/4)^2 + 64T(n/8) \\ &amp;= \cdots
\end{align*}
$$
Note that $n^2 = 4(n/2)^2 = 16(n/4)^2$. If $n = 2^m$ then after $m$ steps we will reach $4^mT(n/2^m) = 4^mT(1)$, with $m$ copies of $n^2$ tagging along. Therefore
$$
T(n) = mn^2 + 4^mT(1) = n^2\log_2 n + n^2 T(1).
$$