Offensive Security Researcher & Quantum Cryptography Analyst

Proof of the Master Theorem: Divide-and-Conquer Recurrences Solved

Abdul Wahab Junaid
Proof of the Master Theorem (Divide-and-Conquer)

I use the Master Theorem constantly whenever I need to figure out the running time of a divide-and-conquer algorithm without grinding through a recurrence by hand every single time. But I don’t just want to use it blindly — I want to understand why it works. In this file, I walk through the actual proof, showing how the theorem falls directly out of analyzing a recursion tree. Understanding the proof gives me the confidence to apply the theorem correctly, and it also tells me exactly why the theorem has three separate cases.

History and Background

The Master Theorem, as it’s taught today, was popularized in its modern form by Cormen, Leiserson, Rivest, and Stein in Introduction to Algorithms, though the underlying idea of analyzing recurrences via recursion trees goes back much further, tracing through the works of Donald Knuth in The Art of Computer Programming (1968) and Jon Bentley, Dorothea Haken, and James Saxe, who published a more generalized version of the theorem in their 1980 paper “A general method for solving divide-and-conquer recurrences.” I think of the Master Theorem as a distilled, easy-to-apply summary of decades of recurrence analysis, boiled down into a formula I can use almost mechanically.

Problem Statement

I want to solve recurrences of the general form:

$$ T(n) = aT\left(\frac{n}{b}\right) + f(n) $$

where $a \geq 1$ and $b > 1$ are constants, and $f(n)$ is an asymptotically positive function. My goal is to find a closed-form asymptotic bound on $T(n)$ without having to expand the recurrence by hand every time.

Core Concepts

How It Works

To prove the theorem, I build the recursion tree for $T(n) = aT(n/b) + f(n)$ and account for the total work done at every level:

  1. At the root (depth 0), the cost is $f(n)$.
  2. At depth 1, there are $a$ subproblems, each of size $n/b$, so the combining cost at this level is $a \cdot f(n/b)$.
  3. At depth $i$, there are $a^i$ subproblems, each of size $n/b^i$, so the combining cost at this level is $a^i \cdot f(n/b^i)$.
  4. The recursion bottoms out when $n/b^i = 1$, i.e., at depth $i = \log_b n$.
  5. At the leaves (depth $\log_b n$), there are $a^{\log_b n} = n^{\log_b a}$ leaves, each contributing a constant cost.
  6. I sum the cost across all levels to get the total running time.

Working Principle

The whole proof reduces to comparing two competing quantities: the cost of the work done to combine subproblems at each level, $f(n)$, versus the cost of the leaves, $n^{\log_b a}$. Whichever one dominates determines the overall asymptotic behavior:

Mathematical Foundation

I start by summing the total cost over the recursion tree:

$$ T(n) = \sum_{i=0}^{\log_b n – 1} a^i f\left(\frac{n}{b^i}\right) + \Theta(n^{\log_b a}) $$

The term $\Theta(n^{\log_b a})$ accounts for the leaves. Now I consider the three cases based on how $f(n)$ compares to $n^{\log_b a}$.

Case 1: $f(n) = O(n^{\log_b a – \epsilon})$ for some $\epsilon > 0$.

Here $f(n)$ grows polynomially slower than $n^{\log_b a}$. I can show the sum $\sum_{i=0}^{\log_b n – 1} a^i f(n/b^i)$ is geometrically dominated by its last term, which is $\Theta(n^{\log_b a})$. So:

$$ T(n) = \Theta(n^{\log_b a}) $$

Case 2: $f(n) = \Theta(n^{\log_b a} \log^k n)$ for some $k \geq 0$.

Here $f(n)$ and $n^{\log_b a}$ grow at (nearly) the same rate. Substituting into the sum, each of the $\log_b n$ levels contributes roughly the same amount, so I pick up an extra logarithmic factor:

$$ T(n) = \Theta(n^{\log_b a} \log^{k+1} n) $$

Case 3: $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$, and the regularity condition $a f(n/b) \leq c f(n)$ holds for some $c < 1$ and sufficiently large $n$.

Here $f(n)$ grows polynomially faster than $n^{\log_b a}$. The regularity condition ensures the sum is dominated by its first term (the root), so:

$$ T(n) = \Theta(f(n)) $$

I can verify the geometric-series argument explicitly. Substituting $n/b^i$ into $f$ under Case 1’s assumption:

$$ \sum_{i=0}^{\log_b n – 1} a^i f\left(\frac{n}{b^i}\right) = O\left(\sum_{i=0}^{\log_b n – 1} a^i \left(\frac{n}{b^i}\right)^{\log_b a – \epsilon}\right) = O\left(n^{\log_b a – \epsilon} \sum_{i=0}^{\log_b n – 1} \left(\frac{a b^\epsilon}{b^{\log_b a}}\right)^i\right) $$

Since $b^{\log_b a} = a$, the ratio inside the sum simplifies to $b^\epsilon > 1$, giving a geometric series that sums to $\Theta((b^\epsilon)^{\log_b n}) = \Theta(n^\epsilon)$. Multiplying back by $n^{\log_b a – \epsilon}$, the sum becomes $\Theta(n^{\log_b a})$, confirming Case 1.

Diagrams

flowchart TD
    A["T(n) = aT(n/b) + f(n)"] --> B["Compare f(n) to n^(log_b a)"]
    B --> C["f(n) smaller: Case 1 -> Θ(n^log_b a)"]
    B --> D["f(n) equal (with log factor): Case 2 -> Θ(n^log_b a · log^(k+1) n)"]
    B --> E["f(n) larger + regularity: Case 3 -> Θ(f(n))"]

graph TD
    R["Depth 0: cost f(n)"] --> L1["Depth 1: a subproblems, cost a·f(n/b)"]
    L1 --> L2["Depth 2: a^2 subproblems, cost a^2·f(n/b^2)"]
    L2 --> LD["..."]
    LD --> LEAF["Depth log_b n: n^(log_b a) leaves, constant cost each"]

Pseudocode

This is a mathematical proof rather than a procedural algorithm, but here is how I’d encode the decision logic when applying the theorem in practice:

MASTER-THEOREM(a, b, f_n_growth_rate, n_log_b_a):
    if f_n_growth_rate is polynomially smaller than n_log_b_a:
        return Θ(n^(log_b a))                     // Case 1
    else if f_n_growth_rate ≈ n_log_b_a * log^k(n):
        return Θ(n^(log_b a) * log^(k+1)(n))       // Case 2
    else if f_n_growth_rate is polynomially larger than n_log_b_a
             and regularity condition holds:
        return Θ(f(n))                             // Case 3
    else:
        return "Master Theorem does not apply"

Step-by-Step Example

Let me walk through $T(n) = 2T(n/2) + n$, the recurrence for merge sort.

This matches what I already know about merge sort’s running time, confirming the theorem’s correctness on a familiar example.

Time Complexity

The Master Theorem itself isn’t an algorithm, so it doesn’t have its own runtime, but applying it is essentially an $O(1)$ operation once I’ve correctly identified $a$, $b$, and $f(n)$ — I just compare growth rates and pick a case.

Space Complexity

Not applicable in the traditional sense, since the theorem is an analytical tool. However, understanding the recursion tree used in the proof does implicitly describe the recursive call stack depth of the underlying algorithm, which is $O(\log_b n)$ levels deep.

Correctness Analysis

The proof’s correctness rests on rigorously bounding the sum over all levels of the recursion tree using geometric series arguments. Case 1 and Case 3 rely on the fact that a geometric series with ratio less than 1 (Case 1) or greater than 1 (Case 3) is dominated by one end of the sum, while Case 2 relies on every term contributing equally, producing a linear number of equal-sized additions across $\log_b n$ levels. Each case’s proof is airtight given its stated conditions, which is exactly why the theorem requires those specific conditions (like the regularity condition in Case 3) to hold.

Advantages

Disadvantages

Applications

Implementation in C

Since the Master Theorem is a mathematical tool, I demonstrate it here as a small utility that classifies a recurrence given $a$, $b$, and the exponent of $f(n) = n^c$ (assuming $f(n)$ is a simple polynomial for demonstration purposes).

#include <stdio.h>
#include <math.h>

/* Classifies T(n) = a*T(n/b) + n^c using the Master Theorem,
   assuming f(n) = n^c (a simple polynomial, no log factors). */
void masterTheorem(double a, double b, double c) {
    double criticalExponent = log(a) / log(b); /* log_b(a) */

    printf("log_b(a) = %.4f\n", criticalExponent);

    if (c < criticalExponent - 1e-9) {
        printf("Case 1: T(n) = Theta(n^%.4f)\n", criticalExponent);
    } else if (fabs(c - criticalExponent) < 1e-9) {
        printf("Case 2: T(n) = Theta(n^%.4f * log n)\n", criticalExponent);
    } else {
        printf("Case 3 (check regularity condition manually): T(n) = Theta(n^%.4f)\n", c);
    }
}

int main() {
    /* Example: merge sort recurrence T(n) = 2T(n/2) + n */
    printf("Merge sort: T(n) = 2T(n/2) + n\n");
    masterTheorem(2, 2, 1);

    printf("\nBinary search: T(n) = T(n/2) + 1\n");
    masterTheorem(1, 2, 0);

    printf("\nStrassen-like: T(n) = 7T(n/2) + n^2\n");
    masterTheorem(7, 2, 2);

    return 0;
}

Sample Input and Output

Running the program above produces:

Merge sort: T(n) = 2T(n/2) + n
log_b(a) = 1.0000
Case 2: T(n) = Theta(n^1.0000 * log n)

Binary search: T(n) = T(n/2) + 1
log_b(a) = 0.0000
Case 2: T(n) = Theta(n^0.0000 * log n)

Strassen-like: T(n) = 7T(n/2) + n^2
log_b(a) = 2.8074
Case 1: T(n) = Theta(n^2.8074)

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version