Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability / 3 / e / ii / Solution

Use the same integer rounding in a divide-and-conquer recurrence, now with root cost $n^2$. Since $1/4\le m/n\le 1/2$,Choose $C\ge \max \{T(1),8/3\}$ and use strong induction with inductive hypothesis $T(j)\le C{j}^2$. Both child sizes are positive and less than $n$, soThe same factor $5/8$ occurs for the exact fractional split. Therefore $\boxed{T(n)=O(n^2)}$ in Big O notation.