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

The printed fractional arguments require a size convention. To make the recurrence relation precise on positive integers, take a bounded base case $T(1)=t>0$ and use $m=\lceil n/4\rceil$, $n-m$ for $n\ge 2$. This integer rounding in a divide-and-conquer recurrence gives $1/4\le m/n\le 1/2$. The unrounded calculation is the special split fraction $1/4$.

Prove $T(n)\le An{\log }_{2}n+Bn$ by strong induction. Put $h_0=H_2(1/4)>0$, choose $A\ge 1/h_0$, and choose $B\ge t$. The base case follows. The entropy potential for a divide-and-conquer recurrence givesThe last step uses $H_2(m/n)\ge h_0$. This closes the inductive hypothesis and proves $\boxed{T(n)=O(n\log n)}$ in Big O notation.

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.