Master Theorem Method

Master Theorem Method

Divide-and-conquer algorithms keep asking the same question: if I split my problem into a few smaller copies of itself, do the same amount of work at each split, and glue the pieces back together — how long does the whole thing take? Writing that down gives a recurrence like T(n) = a·T(n/b) + f(n). Solving such recurrences by hand (drawing the tree, summing every level) is doable but tedious and easy to botch. The Master Theorem is a lookup table for the most common shape of these recurrences: match your recurrence to one of three cases, read off the answer. It turns a page of algebra into a 30-second decision.

The precise statement

The Master Theorem applies to recurrences of the form

T(n) = a·T(n/b) + f(n),   with a ≥ 1, b > 1, and f(n) asymptotically positive.

Here a is the number of subproblems, n/b is the size of each subproblem, and f(n) is the non-recursive work (the split + combine cost) done at each call. The whole method hinges on comparing f(n) against the watershed function nlogba. Intuitively, nlogba counts the leaves of the recursion tree; the comparison asks whether the leaf work or the root work dominates.

• Case 1 — leaves win. If f(n) = O(nlogba − ε) for some constant ε > 0 (f is polynomially smaller), then T(n) = Θ(nlogba).
• Case 2 — a tie. If f(n) = Θ(nlogba), then T(n) = Θ(nlogba · log n). (The extra log n counts the tree's levels.)
• Case 3 — root wins. If f(n) = Ω(nlogba + ε) for some ε > 0, and the regularity condition a·f(n/b) ≤ c·f(n) holds for some c < 1 and large n, then T(n) = Θ(f(n)).

Per-level work, counted: T(n) = 2·T(n/2) + n (Case 2)

Merge sort's recurrence is the canonical Case-2 shape (a=2, b=2, f(n)=n, watershed nlog₂2=n). The reason the answer is Θ(n log n) is that every level of the recursion tree does the same total work n — the split doubles the node count but halves each node's work, so the two effects cancel. Counting for n = 8:

Each of the log₂n = 3 halving levels contributes exactly n = 8, so the combine work totals n · log₂n = 8 × 3 = 24 = Θ(n log n) — identical to the hand-count in the worked example below and to the equal-per-level tree in the diagram above. The per-level sums are equal (8 = 8 = 8), which is precisely the fingerprint of Case 2; if any level's total grew or shrank down the tree you would instead be in Case 3 (root dominates) or Case 1 (leaves dominate). (Numbers verified by direct arithmetic on the recurrence, not asserted by an interactive engine.)

Worked example: Merge Sort, counted

Merge sort splits an array of size n into 2 halves of size n/2, sorts each recursively, then merges them in linear time. So a = 2, b = 2, f(n) = Θ(n).

Compute the watershed: logba = log22 = 1, so nlogba = n1 = n. Now compare f(n) = n against n: they match, f(n) = Θ(n). That is Case 2, giving T(n) = Θ(n1 · log n) = Θ(n log n).

Sanity-check by counting the tree levels for n = 8: level 0 merges once over 8 elements (8 units of work), level 1 has 2 merges of 4 (2×4 = 8), level 2 has 4 merges of 2 (4×2 = 8). Every level does exactly n = 8 units, and there are log28 + 1 = 4 levels. Total ≈ 8 × log28 = 24 — matching n log n. This is why the tie-case log n factor appears: the work is spread evenly across a logarithmic number of levels.

Two more quick reads. Binary search: T(n) = T(n/2) + Θ(1), so a=1, b=2, log21 = 0, watershed n0 = 1; f(n)=Θ(1)=Θ(n0) → Case 2 → Θ(log n). Naïve recursive matrix multiplication T(n)=8T(n/2)+Θ(n2): log28 = 3, watershed n3; f(n)=n2 is polynomially smaller → Case 1 → Θ(n3).

Pitfalls & what an interviewer probes

• The gap in Case 1/3 must be polynomial. "Slightly smaller" isn't enough — you need an nε factor of separation. The classic trap is T(n) = 2T(n/2) + n log n. Here f(n)=n log n is bigger than n but only by a logarithmic factor, not a polynomial nε. The Master Theorem does not apply; the true answer is Θ(n log2 n).
• Case 3 needs the regularity check. Interviewers love asking "is that all?" after you cite Case 3. You must also verify a·f(n/b) ≤ c·f(n) for some c < 1. It almost always holds for polynomial f, but stating it shows rigor.
• Unequal splits break it. T(n)=T(n/3)+T(2n/3)+n (as in some quicksort analyses) is not of Master form — reach for the recursion-tree or Akra–Bazzi method instead.
• Floors/ceilings and the base case don't change the asymptotics — the theorem tolerates ⌊n/b⌋. Don't get distracted by them.
• a and b are independent. A common slip is assuming a = b. In 7T(n/2) (Strassen), a=7, b=2, giving Θ(nlog27) ≈ Θ(n2.81) — the whole point of the algorithm.

When it matters & trade-offs vs. neighbours

The Master Theorem is the fastest correct tool only when your recurrence fits the a·T(n/b)+f(n) mold with a single subproblem size. That covers a huge slice of interview and real-world divide-and-conquer: merge/quick sort, binary search, Karatsuba (3T(n/2)+n → Θ(n1.58)), Strassen, FFT, closest-pair. In these settings it lets you compare design choices instantly — e.g. seeing that reducing a from 8 to 7 in matrix multiply drops you below the n3 barrier.

Its neighbours cover what it can't. The recursion-tree method is slower but always works and builds the intuition the theorem hides — use it when you're unsure or in a gap case. The substitution method (guess + induction) proves bounds the theorem only estimates and handles arbitrary forms. Akra–Bazzi generalizes to unequal splits and multiple terms. Choose the Master Theorem for speed on standard forms; drop to these when the shape doesn't match or the gap isn't polynomial. All of them solve the recurrence you feed them — so make sure the recurrence matches the algorithm on the inputs you care about. For input-oblivious algorithms like merge sort or Karatsuba, the recursion shape is fixed, so best, worst, and average coincide and a single Θ answer suffices (binary search almost qualifies, but a lucky first probe gives it an O(1) best case; its Θ(log n) is the worst/average case). Quicksort is the caution: 2T(n/2)+Θ(n) models only its balanced (best/average) split — its worst case follows T(n-1)+Θ(n) → Θ(n²), a recurrence outside the theorem entirely.

Key takeaways

• For T(n)=a·T(n/b)+f(n), compute the watershed nlogba and compare it to f(n): smaller f → Θ(nlogba), equal → Θ(nlogba log n), larger f → Θ(f(n)).
• The gap in Cases 1 and 3 must be polynomial (nε); a mere log n difference (e.g. 2T(n/2)+n log n) falls in the gap and the theorem doesn't apply.
• Always cite the regularity condition for Case 3, and remember a and b are independent — this distinguishes merge sort (Case 2) from Strassen (Case 1).
• When splits are unequal or the form doesn't fit, fall back to the recursion-tree, substitution, or Akra–Bazzi methods.