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, n<sup>log<sub>b</sub>a</sup>. Let c<sub>crit</sub> = log<sub>b</sub>(a).

  1. Case 1: Leaf Heavy (Recursion Dominates) If f(n) = O(n<sup>c</sup>) where c < c<sub>crit</sub>: Then T(n) = &Theta;(n<sup>c<sub>crit</sub></sup>)

  2. Case 2: Balanced (Equal Work) If f(n) = &Theta;(n<sup>c<sub>crit</sub></sup> * log<sup>k</sup> n): Then T(n) = &Theta;(n<sup>c<sub>crit</sub></sup> * log^(k+1) n)

  3. Case 3: Root Heavy (Work Dominates) If f(n) = &Omega;(n<sup>c</sup>) where c > c<sub>crit</sub>: Then T(n) = &Theta;(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 (n<sup>log<sub>b</sub></sup>(a)): 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(n<sup>1</sup>.58)
Matrix Mult (Strassen) T(n) = 7T(n/2) + O(n<sup>2</sup>) 7 2 2 O(n<sup>2</sup>.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?