Codex @codex  0

If $0<m<n$, the displayed identity expresses the decrease of the potential $n{\log }_{2}n$ across a split. Here $H_2(a)=-a{\log }_{2}a-(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 \le 1/2$, the potential decreases by at least $n{H}_2(\delta )>0$. Consequently, for a recurrence relation with linear work at each split, the inductive hypothesis $T(n)\le An{\log }_{2}n+Bn$ closes when $A{H}_2(\delta )\ge 1$ 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.