Masters Theorem proof

Extended proof from CLRS for master theorem

Proof for 3 statements

Statement 1

If \(a ⋅ f(n/b) ≤ αf(n)\) for some \(α < 1\), then \(T(n) = O( f(n))\)

Intuitively, the statement says that each time we split, the increased in the combined runtime of the child node \(af(n/b)\) is less than the their parent \(α f(n)\).

From the recursion tree we know that:

$$\begin{split} T(n) = T(n) &= a^{L+1}T(1) + \sum_{i=0}^{L} a^i f(n/b^i) \\ &= \Theta(\sum_{i = 0}^{L} a^i f(n/b^i)) \end{split}$$

We can inductively find an upper bound for all elements of the set \(\{a^i f(n / b^i) | i ∈ ℤ \}\) :

$$\begin{split} a^i ⋅ f(n / b^i ) &≤ α ⋅ a^{i− 1} ⋅ f(n/b^{i− 1}) \\ &≤ α^2 ⋅ a^{i− 2} ⋅ f(n / b^{i− 2}) \\ &≤ ⋯ \\ &≤ α^i f(n ) \ \ \ \ (upper \ bound) \end{split}$$

Conclusion (as \(L -> ∞\)):

$$\begin{split} \sum_{i=0}^{L} a^i f (n / b^i) &\leq \sum_{i=0}^{L} a^i f (n) \\ &\leq \frac{1}{1-a} f(n) \\ &= O(f(n)) \end{split}$$

Statement 2

If \(a · f(n/b) \geq βf(n)\) for some \(β>1\), then \(T(n) = O(a^{log_{b}{n}})\)

Intuitively, the statement says that each time we split, the runtime increases. Hence the deeper the depth, it becomes exponenetially more significant.

The greatest runtime (limit) will be when the most possible splits occur (i is maximum).

Expanding the inequality above:

$$\begin{split} f(n) &\leq \frac{a}{β} · f(n/b) \\ &\leq (\frac{a}{β})^2 · f(n/b^2) \\ &... \\ &\leq (\frac{a}{β})^L · f(n/b^L) \\ \end{split}$$

We then realize: $$\begin{split} f(n) &\leq (\frac{a}{β})^L · f(n/b^L) \\ a · f(n/b) &\leq (\frac{a^L}{β^{L - 1}}) · f(n/b^L) \\ a^2 · f(n/b^2) &\leq (\frac{a^L}{β^{L - 2}}) · f(n/b^L) \\ &... \\ a^L · f(n/b^L) &\leq (\frac{a^L}{β^{L - L}}) · f(n/b^L) \\ \end{split}$$

Establishing relation (simplify the Geometric series ):

$$\begin{split} \sum_{i = 0}^{L} a^i f(n / b^i) &\leq (a^L · f(n/b^L)) \sum_{i = 0}^{L} (\frac{1}{β})^i \\ &\leq (a^L · f(n/b^L)) (\frac{β - 1}{β}) \\ &\leq (a^L · f(n/b^L)) \end{split}$$

Largest possible value of \(L\) is at \(f(1)\), i.e. \(L = log_bn\)

Then, $$\begin{split} \sum_{i = 0}^{L} a^i f(n / b^i) &\leq (a^L · f(n/b^L)) \\ &\leq (a^{log_bn} · f(1)) \\ &\leq (a^{log_bn}) \\ \end{split}$$

Hence,

$$ T(n) = (a^{log_bn}) $$