Master Theorem

A divide-and-conquer algorithm describes its own cost in terms of itself. Merge sort sorts an array by sorting two half-arrays and merging the results, so its running time obeys T(n) = 2T(n/2) + n. That equation is called a recurrence relation, and it is not an answer — you cannot look at it and say how fast merge sort is.

Solving the recurrence means turning it into a closed form like Θ(n log n). There are three standard ways to do that: expand it into a recursion tree and sum the levels, guess an answer and prove it by induction (the substitution method), or — when the recurrence has the right shape — apply the Master Theorem and simply read the answer off. This page is about the third.

The theorem applies to recurrences that can be written in exactly this shape:

• a — how many subproblems each call creates.
  • Merge sort makes two recursive calls, so a = 2. It must be a constant ≥ 1; it does not have to equal b.
• b — the factor by which the input shrinks.
  • Halving the array means b = 2. It must be a constant greater than 1, otherwise the recursion never reaches the base case.
• f(n) — everything the call does outside the recursion.
  • The splitting, the merging, the partitioning, the combining. For merge sort this is the O(n) merge.

If your recurrence does not fit this template — different-sized subproblems, a subtractive step, a non-constant a — the Master Theorem does not apply, and no amount of rearranging will change that. The section on limitations below covers what to do instead.

In practice you extract the recurrence from the function body. Every recursive call contributes to a and b; everything else contributes to f(n):

function mergeSort(arr) {
  if (arr.length <= 1) return arr;              // base case: O(1)

  const mid  = Math.floor(arr.length / 2);
  const left  = mergeSort(arr.slice(0, mid));   // a = 2 calls
  const right = mergeSort(arr.slice(mid));      // b = 2 (half the size)

  return merge(left, right);                    // f(n) = O(n)
}

function binarySearch(arr, target, low, high) {
  if (low > high) return -1;                    // base case: O(1)

  const mid = Math.floor((low + high) / 2);     // f(n) = O(1)
  if (arr[mid] === target) return mid;

  return arr[mid] < target                      // a = 1 call
    ? binarySearch(arr, target, mid + 1, high)  // b = 2 (half the range)
    : binarySearch(arr, target, low, mid - 1);
}

Picture the recursion as a tree. The root is the original problem, each node has a children, and sizes shrink by a factor of b as you descend:

The recursion stops when the size reaches 1, which takes log_b n levels, and the bottom level holds n^(log_b a) leaves. So the total cost is a contest between two quantities: the work at the leaves, which is Θ(n^(log_b a)), and the work at the root, which is f(n).

That contest has exactly three outcomes, and those outcomes are the three cases. Either the leaves win, or the root wins, or neither does and every level contributes equally.

The function n^(log_b a) that f is compared against is sometimes called the watershed function. Computing it is always the first step, because all three conditions are stated relative to it.

The ε in Cases 1 and 3 matters more than it looks. It requires f to be polynomiallysmaller or larger — smaller or larger by a factor of n^ε for some ε > 0. Being smaller by a factor of log n does not qualify, and that is precisely the gap where the theorem gives no answer at all.

Case 2 also has a commonly used extended form: if f(n) = Θ(n^(log_b a) · log^k n) for some k ≥ 0, then T(n) = Θ(n^(log_b a) · log^(k+1) n). This is what handles T(n) = 2T(n/2) + n log n, giving Θ(n log² n).

Solve T(n) = 2T(n/2) + n.

1. Identify the parts.
   • a = 2, b = 2, f(n) = n.
2. Compute the watershed function.
   • n^(log_b a) = n^(log₂2) = n¹ = n.
3. Compare.
   • f(n) = n and the watershed is n. They are the same, so Case 2 applies.
4. Apply Case 2.
   • T(n) = Θ(n^(log_b a) · log n) = Θ(n log n).

This matches the recursion tree above: every level costs n, and there are log₂n levels.

Solve T(n) = 4T(n/2) + n.

1. Identify the parts.
   • a = 4, b = 2, f(n) = n.
2. Compute the watershed function.
   • n^(log₂4) = n² — four subproblems of half the size produce n² leaves.
3. Compare.
   • f(n) = n is polynomially smaller than n²: n = O(n^(2−ε)) with ε = 1. Case 1 applies.
4. Apply Case 1.
   • T(n) = Θ(n^(log_b a)) = Θ(n²).

The linear work at the root is irrelevant here — the tree branches so fast that almost all the cost sits in the leaves.

Solve T(n) = 2T(n/2) + n².

1. Identify the parts.
   • a = 2, b = 2, f(n) = n².
2. Compute the watershed function.
   • n^(log₂2) = n.
3. Compare.
   • f(n) = n² is polynomially larger than n: n² = Ω(n^(1+ε)) with ε = 1. Case 3 is a candidate.
4. Check the regularity condition.
   • a·f(n/b) = 2·(n/2)² = n²/2 ≤ c·n² holds with c = 1/2 < 1, so the condition is satisfied.
5. Apply Case 3.
   • T(n) = Θ(f(n)) = Θ(n²).

Here the quadratic work at the top level swamps everything below it, so the recursion contributes nothing asymptotically.

Strassen's matrix multiplication is the most interesting row. It replaces eight recursive multiplications with seven, dropping a from 8 to 7 — and since the answer is Θ(n^(log₂a)), that single change takes the running time from Θ(n³) to roughly Θ(n^2.807). It is a direct, practical demonstration that a is the parameter worth fighting over.

1. Put the recurrence in standard form and read off a, b and f(n).
   • T(n) = aT(n/b) + f(n), with a ≥ 1 and b > 1 both constant.
2. Compute the watershed function n^(log_b a).
   • This is the total cost of the leaves. Use log_b a = log a / log b if the exponent is not obvious.
3. Compare f(n) with n^(log_b a).
   • Polynomially smaller → Case 1. The same → Case 2. Polynomially larger → Case 3.
4. For Case 3 only, verify the regularity condition.
   • a · f(n/b) ≤ c · f(n) for some constant c < 1 and all large n.
5. Write the answer that the matching case gives you.
   • Case 1 → Θ(n^(log_b a)); Case 2 → Θ(n^(log_b a) log n); Case 3 → Θ(f(n)).

The theorem is narrow by design, and recognising when it does not fit is as important as applying it when it does:

The first row is the classic gap case. Here f(n) = n/log n is smaller than the watershed n, but only by a logarithmic factor, not a polynomial one — so Case 1 does not apply, and it is not equal to n either, so Case 2 does not apply. The theorem is simply silent, and you need a recursion tree to find the real answer.

• Forgetting that the difference must be polynomial.
  • Case 1 needs f to be smaller by a factor of n^ε for some ε > 0. Being smaller by a factor of log n is not enough, and that recurrence falls into the gap where the theorem says nothing.
• Skipping the regularity condition in Case 3.
  • It holds for every polynomial f, which is why it is easy to forget — but it is part of the case, and there are standard exercises built on functions where it fails.
• Applying it to subtract-and-conquer recurrences.
  • T(n) = T(n − 1) + n is not of the form aT(n/b) + f(n). The Master Theorem cannot touch it.
• Mixing up a and b.
  • a is how many calls you make; b is how much smaller each one is. In T(n) = 4T(n/2) + n they are different numbers, and swapping them changes the answer from Θ(n²) to Θ(n log n).
• Worrying about floors and ceilings.
  • T(⌊n/2⌋) and T(⌈n/2⌉) give the same asymptotic answer as T(n/2). You can safely ignore them.
• Assuming the theorem covers every divide-and-conquer algorithm.
  • Quick sort's worst case is T(n) = T(n − 1) + n, and its average case involves unequal splits. Neither is a Master Theorem problem.

• The Master Theorem solves T(n) = aT(n/b) + f(n) for constant a ≥ 1 and b > 1.
• Everything hinges on comparing f(n) with the watershed function n^(log_b a).
• Case 1: leaves dominate → Θ(n^(log_b a)). Case 2: levels tie → Θ(n^(log_b a) log n). Case 3: root dominates → Θ(f(n)).
• The difference in Cases 1 and 3 must be polynomial; a log factor is not enough, and that gap is where the theorem stays silent.
• Case 3 is not finished until you have checked the regularity condition a·f(n/b) ≤ c·f(n).
• Unequal splits, subtractive recurrences and non-constant a all fall outside the theorem — reach for a recursion tree instead.