Proof of the Master’s Theorem for Dividing Function

17 Dec, 2024

This is a simplified version of the proof of the Master’s Theorem for Dividing Functions. The gist of the proof lies in the rules of big-O notation—the bigger term “eats” the smaller term. Follow this proof and you’ll see how that applies.

Definition. Master Theorem for Dividing Function:

$T(n)=aT\left({\displaystyle \frac{n}{b}}\right)+f(n)$, where $f(n)\sim n^k{\log }^{p}n$:

Case 1: If ${\log }_{b}a>k$, then $T(n)=O(n^{{\log }_{b}a})$.

Case 2: If ${\log }_{b}a=k$, then:

Case 2-1: If $p<-1$, then $T(n)=O(n^k)$.

Case 2-2: If $p>-1$, then $T(n)=O(n^k{\log }^{p+1}n)=O(f(n)\log n)$.

Case 2-3: If $p=-1$, then $T(n)=O(n^k\log (\log n))$.

Case 3: If ${\log }_{b}a<k$, and $f(n)$ satisfies the additional condition $af\left({\displaystyle \frac{n}{b}}\right)\le cf(n)$ for some constant $0<c<1$, then $T(n)=O(f(n))$.

Proof.

By the summation of the recursion tree with the height $h={\log }_{b}n$:

${\displaystyle T(n)=\sum _{i=0}^h{a}^{i}f\left({\displaystyle \frac{n}{b^i}}\right)+O(a^h)}$.

The first term is all nodes except the leaves, the second term is the leaves.

Since $a^h=a^{{\log }_{b}n}=n^{{\log }_{b}a}$, and substitute $f(n)$ with $n^k{\log }^{p}n$, we have

${\displaystyle T(n)=\sum _{i=0}^h{a}^i{\left({\displaystyle \frac{n}{b^i}}\right)}^k{\log }^p\left({\displaystyle \frac{n}{b^i}}\right)+O(n^{{\log }_{b}a})}$.

$\log \left({\displaystyle \frac{n}{b^i}}\right)=\log \left(b^{{\log }_{b}n-i}\right)=\log (b^{h-i})\sim {\log }_b(b^{h-i})=h-i$.

Thus the first term ${\displaystyle \sum _{i=0}^h{a}^i{\left({\displaystyle \frac{n}{b^i}}\right)}^k{\log }^p\left({\displaystyle \frac{n}{b^i}}\right)\sim n^k\sum _{i=0}^h{a}^i{b}^{-ik}(h-i{)}^p}$.

Case 1

If ${\log }_{b}a>k$, and because the first term would not exceed $O(n^k{\log }_b^{p}n)$ which grows slower than the second term $O(n^{{\log }_{b}a})$, thus

$T(n)=O(n^{{\log }_{b}a})$.

Case 2

If ${\log }_{b}a=k$, then $a^i{b}^{-ik}=a^i{b}^{-i{\log }_{b}a}=a^i{a}^{-i}=1$,

the first term becomes ${\displaystyle n^k\sum _{i=0}^h(h-i{)}^p=n^k\sum _{i=0}^h{i}^p}$.

A handy supporting lemma:

${\displaystyle \sum _{i=0}^{\infty }{i}^p}$ converges if $p<-1$ (harmonic series) and diverges otherwise;

${\displaystyle \sum _{i=0}^h{i}^p\approx \{\begin{array}{cc}\ln h+\gamma ,\hfill & \text{if }p=-1,\hfill \\ {\displaystyle \frac{h^{p+1}}{p+1}},\hfill & \text{if }p>-1.\hfill \end{array}}$

($\gamma$ is the Euler–Mascheroni constant.)

Case 2-1

If $p<-1$, then ${\displaystyle \sum _{i=0}^h{i}^p<c}$ for some constant $c$,

thus the first term reduces to $c\cdot n^k$, and $T(n)=O(n^k)$.

Hence $T(n)=O(n^k\log (\log n)+n^k)=O(n^k\log (\log n))$.

Case 2-2

If $p>-1$, the first term $\sim n^k{h}^{p+1}=n^k{\log }_b^{p+1}n\sim n^k{\log }^{p+1}n$.

Hence $T(n)=O(n^k{\log }^{p+1}n+n^k)=O(n^k{\log }^{p+1}n)$.

Case 2-3

If $p=-1$, the first term $\sim n^k\ln h=n^k\ln ({\log }_{b}n)\sim n^k\log (\log n)$.

Case 3

If ${\log }_{b}a<k$, then $f(n)\sim n^k{\log }^{p}n>O(n^{{\log }_{b}a})$.

And with the additional condition $af\left({\displaystyle \frac{n}{b}}\right)\le cf(n)$ for some constant $0<c<1$, the first term ${\displaystyle \sum _{i=0}^h{a}^{i}f\left({\displaystyle \frac{n}{b^i}}\right)\le \sum _{i=0}^h{c}^{i}f(n)=f(n)\sum _{i=0}^h{c}^i}$

${\displaystyle \le f(n)\sum _{i=0}^{\infty }{c}^i=f(n)\cdot {\displaystyle \frac{1}{1-c}}=O(f(n))}$. (Geometric series)

Thus, $T(n)=O(f(n))+O(n^{{\log }_{b}a})=O(f(n))$.

Reference materials:

• https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/mm-proof.pdf
• http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/extended_master_theorem.pdf

#Algorithms