= Solution
Use the same <integer rounding in a divide-and-conquer recurrence>, now with root cost $n^2$. Since $1/4\leq m/n\leq1/2$,
$$
m^2+(n-m)^2\leq\frac58n^2.
$$
Choose $C\geq\max\{T(1),8/3\}$ and use <strong induction> with <inductive hypothesis> $T(j)\leq Cj^2$. Both child sizes are positive and less than $n$, so
$$
T(n)\leq C\{m^2+(n-m)^2\}+n^2
\leq\left(\frac58C+1\right)n^2
\leq Cn^2.
$$
The same factor $5/8$ occurs for the exact fractional split. Therefore $\boxed{T(n)=O(n^2)}$ in <Big O notation>.
Back to article page
