Recursion tree

A recursion tree records recursive calls as nodes and their direct recursive subcalls as children. Its node labels can record the work done outside those subcalls. Summing the work over levels or charging it to nodes proves a total running time bound. For $T(n)=aT(n/b)+f(n)$, level $j$ has approximately $a^j$ instances of size $n/b^j$, so its nonrecursive work is $a^{j}f(n/b^j)$. Summing those quantities explains the cases of the master theorem.

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.