Skip to content
Data Structures and Algorithms / Analysis Foundations and the Design Loop

Proof of the Master Theorem

Divide-and-Conquer, Recurrences, and the Master Theorem stated the master theorem's three cases as a lookup table; this note carries the recursion-tree argument that proves them, so the theorem is not a black box the first time it decides which term dominates a recurrence you did not anticipate. The proof is given for the clean case where nn is an exact power of bb (so every level's subproblem sizes are integers); CLRS extends it to the floor/ceiling case with the same ideas plus bookkeeping, which is sketched but not fully carried here.
Learning objectives. By the end of this note you should be able to:
  • expand the recursion tree for T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n) and write down the cost at an arbitrary level ii;
  • sum the per-level costs into a single expression and identify which term (the leaves or the root) dominates in each of the three regimes;
  • explain, without consulting the theorem's statement, why the boundary case (f(n)=Θ(nlog⁡ba)f(n) = \Theta(n^{\log_b a})) picks up an extra log⁡n\log n factor.

In this lesson

  1. Setting up the recursion tree
  2. Case 1: the leaves dominate
  3. Case 2: every level costs the same
  4. Case 3: the root dominates

Before you start

The full lesson, with worked examples and exercise solutions, is for members.

Read the full lesson

New to SelfMadeQuant.com? See membership options or explore the curriculum.