= Solution
We prove the stronger bound $T(n)\leq2n^2$ for every $n\geq1$ by <strong induction>. The initial case is $T(1)=1\leq2$. For $n\geq2$, put $m=\lfloor n/2\rfloor$. Then $1\leq m<n$, so the induction hypothesis and the defining <recurrence relation> give
$$
T(n)=2T(m)+n^2\leq4m^2+n^2\leq4(n/2)^2+n^2=2n^2.
$$
Thus
$$
\boxed{T(n)\leq2n^2\ (n\geq1),\qquad T(n)=O(n^2).}
$$
The <recurrence relation> must be read as applying for $n\geq2$; applying it at $n=1$ would invoke $T(0)$ outside the printed <domain>. No value of $T(0)$ is needed.
Back to article page
