Master Theorem

[!NOTE] The Master Theorem provides a cookbook method for solving recurrences of the form T(n) = a T(n/b) + f(n), which often arise in divide-and-conquer algorithms.

1. The Formula

Most recursive algorithms can be described by this recurrence:

T(n) = a × T(n/b) + f(n)

Where:

  • n: Size of the problem.
  • a: Number of sub-problems in the recursion (a ≥ 1).
  • b: Factor by which the sub-problem size is reduced (b > 1).
  • f(n): Cost of the work done outside the recursive calls (dividing and combining).

2. The 3 Cases

We compare the work at the root, f(n), with the work at the leaves, nlogba. Let ccrit = logb(a).

  1. Case 1: Leaf Heavy (Recursion Dominates) If f(n) = O(nc) where c < ccrit: Then T(n) = Θ(nccrit)

  2. Case 2: Balanced (Equal Work) If f(n) = Θ(nccrit * logk n): Then T(n) = Θ(nccrit * logk+1 n)

  3. Case 3: Root Heavy (Work Dominates) If f(n) = Ω(nc) where c > ccrit: Then T(n) = Θ(f(n))

3. Interactive Calculator

Input your recurrence parameters to instantly find the time complexity.

Master Theorem Calculator

T(n) = 2 T(n / 2) + O(n1)
Critical Exponent (logb a):
1.00
vs
Work Exponent (d):
1.00
Case 2: Balanced
T(n) = Θ(n log n)

4. Intuition: Who Wins the Tug-of-War?

Think of it as a competition between two forces:

  1. The Recursion (nlogba): How fast the number of leaves grows.
  2. The Work (f(n)): How much work is done at each step.
  • If the Leaves grow faster, the recursion dominates (Case 1).
  • If the Work grows faster, the root work dominates (Case 3).
  • If they grow at the same rate, we multiply by log n (Case 2).

Common Examples

Algorithm Recurrence a b d Result
Binary Search T(n) = T(n/2) + O(1) 1 2 0 O(log n)
Merge Sort T(n) = 2T(n/2) + O(n) 2 2 1 O(n log n)
Karatsuba T(n) = 3T(n/2) + O(n) 3 2 1 O(n1.58)
Matrix Mult (Strassen) T(n) = 7T(n/2) + O(n2) 7 2 2 O(n2.81)

5. Deep Dive Strategy Lab: Master Theorem

Intuition Through Analogy

Think of this chapter like trying all lock combinations safely. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?