= Integer rounding in a divide-and-conquer recurrence
{title2=$m=\lceil n/4\rceil,\quad n-m$}
An integer-valued problem size requires integer subproblem sizes and a base case. For the displayed unequal split with $n\geq2$, both children have positive size less than $n$, and $1/4\leq m/n\leq1/2$. The <entropy potential for a divide-and-conquer recurrence> therefore supplies a uniform positive potential decrease. The squared sizes satisfy $m^2+(n-m)^2\leq5n^2/8$, which similarly closes a quadratic <inductive hypothesis> when the work at the root is $n^2$.
Back to article page
