= Entropy potential for a divide-and-conquer recurrence
{title2=$n\log_2n-m\log_2m-(n-m)\log_2(n-m)=nH_2(m/n)$}
If $0<m<n$, the displayed identity expresses the decrease of the potential $n\log_2n$ across a split. Here $H_2(a)=-a\log_2a-(1-a)\log_2(1-a)$ is the <binary entropy function>. If every split fraction stays in $[\delta,1-\delta]$ for a fixed $0<\delta\leq1/2$, the potential decreases by at least $nH_2(\delta)>0$. Consequently, for a <recurrence relation> with linear work at each split, the <inductive hypothesis> $T(n)\leq A n\log_2n+B n$ closes when $A H_2(\delta)\geq1$ and $B$ covers the base cases. This is a proof by the <substitution method for a recurrence> of an $O(n\log n)$ <time complexity> bound without requiring equal subproblem sizes.
Back to article page
