= Solution
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\geq2$. This <integer rounding in a divide-and-conquer recurrence> gives $1/4\leq m/n\leq1/2$. The unrounded calculation is the special split fraction $1/4$.
Prove $T(n)\leq A n\log_2n+B n$ by <strong induction>. Put $h_0=H_2(1/4)>0$, choose $A\geq1/h_0$, and choose $B\geq t$. The base case follows. The <entropy potential for a divide-and-conquer recurrence> gives
$$
\begin{aligned}
T(n)
&\leq A\{m\log_2m+(n-m)\log_2(n-m)\}+Bn+n\\
&=A n\log_2n+Bn+n\{1-AH_2(m/n)\}\\
&\leq A n\log_2n+Bn.
\end{aligned}
$$
The last step uses $H_2(m/n)\geq h_0$. This closes the <inductive hypothesis> and proves $\boxed{T(n)=O(n\log n)}$ in <Big O notation>.
Back to article page
