The Master Theorem for Recurrence Relations, Explained

Quick Answer

The Master Theorem is a shortcut for finding the time complexity of recursive algorithms shaped like T(n) = a*T(n/b) + f(n), a problem of size n splitting into a subproblems of size n/b, plus f(n) work to combine them. Instead of expanding the recursion by hand, you compare f(n) against n raised to the power log_b(a), and one of three cases tells you the answer directly.

Why recurrences show up everywhere in recursive code

Any recursive algorithm that splits its input into smaller pieces, solves each piece, and then combines the results, has a running time you can describe as a recurrence relation: a formula for T(n) (the time to solve a problem of size n) written in terms of T applied to smaller inputs. Merge sort is the textbook example: it splits an array of size n into two halves, recursively sorts each half, then merges them, giving T(n) = 2*T(n/2) + O(n), two subproblems of half the size, plus linear work to merge.

Binary search gives a simpler recurrence, T(n) = T(n/2) + O(1), one subproblem of half the size, plus constant work to decide which half to recurse into. A naive recursive algorithm that solves two full-size subproblems with heavy combination work, say T(n) = 8*T(n/2) + O(n^2), has the same general shape but a very different growth rate.

Expanding any of these by hand, writing out the recursion tree level by level and summing the work at each level, works, but it's slow and error-prone for anything beyond the simplest cases. The Master Theorem exists specifically to skip that expansion and read the answer off directly, for the large and genuinely common class of recurrences that fit its T(n) = a*T(n/b) + f(n) shape.

A fourth example worth knowing, because it shows up constantly in discussions of "why is this algorithm faster than the obvious one": Karatsuba's multiplication algorithm for large numbers has the recurrence T(n) = 3*T(n/2) + O(n), splitting each number into two halves and combining with three recursive multiplications instead of the four a naive digit-by-digit approach would need. That single difference, three recursive calls instead of four, is the entire reason Karatsuba multiplication beats grade-school long multiplication asymptotically, and the Master Theorem is exactly the tool that turns "three instead of four" into a precise statement about how much faster the algorithm actually is.

The three cases, in plain English

For a recurrence T(n) = a*T(n/b) + f(n), where a >= 1 and b > 1, compute the single quantity n^(log_b(a)), this represents the total work done across all the recursive calls themselves, ignoring the combination cost f(n) for a moment. Then compare it against f(n):

Case 1: the recursive calls dominate

If f(n) grows strictly slower than n^(log_b(a)) (formally, f(n) = O(n^(log_b(a) - epsilon)) for some epsilon > 0), the recursive calls do more total work than the combination step, and T(n) = Theta(n^(log_b(a))). The combination cost barely matters, the sheer number and size of subproblems is what dominates.

Case 2: they're balanced

If f(n) grows at the same rate as n^(log_b(a)) (more precisely, f(n) = Theta(n^(log_b(a)) * log^k(n)) for some k >= 0), the two forces are balanced across every level of the recursion tree, and T(n) = Theta(n^(log_b(a)) * log^(k+1)(n)). This is the case merge sort falls into, with k=0, giving the familiar Theta(n log n).

Case 3: the combination step dominates

If f(n) grows strictly faster than n^(log_b(a)) (formally, f(n) = Omega(n^(log_b(a) + epsilon)) for some epsilon > 0), and a technical "regularity condition" holds, which almost every f(n) you'll encounter in practice satisfies, the combination step dominates, and T(n) = Theta(f(n)). The recursive structure barely matters here, the per-call work outweighs it.

A genuinely useful mental shortcut: think of n^(log_b(a)) as "how much work the branching structure alone generates" and f(n) as "how much work each level's combination step costs". Whichever one grows faster, wins, and case 2 is just the tie.

A rough physical analogy some people find useful: imagine the recursion tree as an organisation chart, where n^log_b(a) measures the total headcount doing recursive sub-work, while f(n) measures how much coordination overhead each level personally handles. If the workforce (the recursive calls) vastly outnumbers the coordination overhead, the workforce's total effort dominates the bill, Case 1. If each level's personal overhead is just as large as the total workforce below it, the two costs are genuinely comparable at every level, Case 2. And if the coordination overhead itself balloons faster than the workforce can grow, the overhead swallows everything else, Case 3.

Working through merge sort by hand

Merge sort's recurrence is T(n) = 2*T(n/2) + O(n). Here a=2 (two recursive calls), b=2 (each handles half the input), and f(n) = n (the linear-time merge step).

Compute n^(log_b(a)) = n^(log_2(2)) = n^1 = n. Compare that against f(n) = n, they match exactly, with k=0 extra logarithmic factor. That's Case 2, so T(n) = Theta(n^1 * log^1(n)) = Theta(n log n).

Binary search's recurrence is T(n) = T(n/2) + O(1). Here a=1, b=2, f(n) = 1 (constant work per call). n^(log_b(a)) = n^(log_2(1)) = n^0 = 1, which matches f(n) = 1 exactly, again Case 2 with k=0, giving T(n) = Theta(log n).

Now a less friendly example: T(n) = 8*T(n/2) + O(n^2), say a naive recursive algorithm that makes 8 half-size recursive calls with quadratic combination work. n^(log_b(a)) = n^(log_2(8)) = n^3. Since f(n) = n^2 grows strictly slower than n^3, that's Case 1, so T(n) = Theta(n^3), the branching factor dominates completely, and the quadratic combination step is essentially noise by comparison.

And the reverse: T(n) = 2*T(n/2) + O(n^2). n^(log_b(a)) = n^1, while f(n) = n^2 grows strictly faster, so that's Case 3, giving T(n) = Theta(n^2), the combination step now dominates and the recursive structure barely matters.

One more worked example shows why the log^k(n) term in Case 2 matters, not just the plain log(n) version most courses lead with. Consider T(n) = 2*T(n/2) + O(n log n), which shows up in certain divide-and-conquer algorithms whose combination step itself needs a sort. Here n^log_b(a) = n^log_2(2) = n, and f(n) = n log n grows faster than n by exactly one logarithmic factor (k=1 in the Case 2 condition), so the result is T(n) = Theta(n * log^2(n)). Missing this generalized form of Case 2 is a common source of wrong answers when a recurrence's combination step isn't simply linear.

Verifying this with code, not just algebra

Algebra is convincing, but it's worth actually counting the work a recursion generates rather than trusting the formula blindly. Here's a small function that counts how many base-case leaves a recursion tree for T(n) = a*T(n/b) actually produces, which should match a^(log_b(n)) exactly (the total number of leaves when you branch a ways, log_b(n) levels deep):

def count_calls(n, a, b):
    """Counts recursion-tree leaves for T(n) = a*T(n/b) + f(n)."""
    if n <= 1:
        return 1
    total = 0
    for _ in range(a):
        total += count_calls(n // b, a, b)
    return total

Running this for the four recurrences discussed above, at n=64:

T(n)=2T(n/2)+n  -> merge sort
  a=2, b=2, f(n)=n^1  =>  n^log_b(a) = n^1.000
  predicted: Case 2: Theta(n log n)
  actual recursion-tree leaf count at n=64: 64  (compare to a^log_b(n) = 64.0)

T(n)=T(n/2)+1   -> binary search
  a=1, b=2, f(n)=n^0  =>  n^log_b(a) = n^0.000
  predicted: Case 2: Theta(log n)
  actual recursion-tree leaf count at n=64: 1  (compare to a^log_b(n) = 1.0)

T(n)=8T(n/2)+n^2
  a=8, b=2, f(n)=n^2  =>  n^log_b(a) = n^3.000
  predicted: Case 1: Theta(n^3), f(n) dominated
  actual recursion-tree leaf count at n=64: 262144  (compare to a^log_b(n) = 262144.0)

T(n)=2T(n/2)+n^2
  a=2, b=2, f(n)=n^2  =>  n^log_b(a) = n^1.000
  predicted: Case 3: Theta(n^2), f(n) dominates
  actual recursion-tree leaf count at n=64: 64  (compare to a^log_b(n) = 64.0)

Every single case lines up exactly: the T(n)=2T(n/2)+n and T(n)=2T(n/2)+n^2 recurrences both produce 64 leaves (matching a^log_b(n) = 2^log_2(64) = 2^6 = 64), the binary-search-shaped recurrence produces exactly 1 leaf (since a=1, there's only ever one branch), and the T(n)=8T(n/2)+n^2 recurrence produces 262,144 leaves, exactly 8^6, confirming the n^3 branching-factor blow-up the Master Theorem predicted for that case.

It's worth being explicit about what this leaf-counting experiment does and doesn't prove. It directly confirms the branching-factor arithmetic behind n^log_b(a), the number of leaves a recursion of this shape actually produces, matches the formula exactly, with no hand-waving. It doesn't, on its own, account for the combination cost f(n) at each internal node of the tree, which is the other half of the Master Theorem's reasoning and exactly what the merge sort comparison-counting experiment in the next section measures instead. Together, the two experiments verify both halves of the theorem's claim independently, rather than trusting either the branching-factor formula or the combination-cost reasoning blindly.

Real merge sort comparison counts vs. the Theta(n log n) prediction

Leaf-counting confirms the recursive branching structure, but it's even more convincing to instrument an actual, working merge sort and count real comparisons as it sorts real arrays:

def merge_sort_count(arr):
    comparisons = [0]
    def merge_sort(a):
        if len(a) <= 1:
            return a
        mid = len(a) // 2
        left = merge_sort(a[:mid])
        right = merge_sort(a[mid:])
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            comparisons[0] += 1
            if left[i] <= right[j]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
        merged.extend(left[i:]); merged.extend(right[j:])
        return merged
    return merge_sort(arr), comparisons[0]

Run against randomly shuffled arrays of increasing size, each result checked against Python's own sorted() to confirm correctness before counting comparisons:

n=   16  actual comparisons=    46  n*log2(n) predicted~=    64.0  ratio=0.719
n=   64  actual comparisons=   305  n*log2(n) predicted~=   384.0  ratio=0.794
n=  256  actual comparisons=  1709  n*log2(n) predicted~=  2048.0  ratio=0.834
n= 1024  actual comparisons=  8966  n*log2(n) predicted~= 10240.0  ratio=0.876
n= 4096  actual comparisons= 43943  n*log2(n) predicted~= 49152.0  ratio=0.894

The actual comparison counts sit consistently below the n*log2(n) line, between about 72% and 89% of the predicted value across this range, and the ratio climbs steadily toward 1 as n grows. That's expected and correct: Theta(n log n) describes the asymptotic growth rate, not an exact comparison count, and the constant factor for merge sort's comparisons is known to be somewhat below 1 by a more detailed accounting, which explains why the ratio keeps closing the gap but not reaching exactly 1.000 even at n=4096. The key thing the Master Theorem promises, and what this data confirms, is the growth shape: as n scales up, the real comparison count tracks n log n, not n^2 and not n, which is the entire point of the theorem.

When the Master Theorem doesn't apply

The theorem only covers recurrences of the exact form T(n) = a*T(n/b) + f(n), with a >= 1 and b > 1 both constants. Several common, genuinely important recurrences fall outside that shape, and reaching for the Master Theorem on them anyway produces nonsense:

• Unequal subproblem sizes. T(n) = T(n/3) + T(2n/3) + O(n), the recurrence for a certain quicksort partition pattern, doesn't fit the single-ratio a*T(n/b) shape. This needs the more general Akra-Bazzi method, or a direct recursion-tree argument.
• Subtractive recurrences. T(n) = T(n-1) + O(1), common in simple linear recursion, isn't of the T(n/b) divide-by-a-constant-factor form at all, it's T(n) = Theta(n) by direct summation, no Master Theorem needed or applicable.
• Non-polynomial f(n). If f(n) grows faster than any polynomial, or oscillates (not simply increasing), the comparison the theorem relies on, and the "regularity condition" for Case 3, can fail to hold cleanly. The extended version of the theorem handles some of these with more careful case analysis, but the simple three-case version taught in most courses doesn't.

Quicksort is actually a good example of both sides of this boundary in one algorithm. Its average-case recurrence, assuming roughly balanced partitions, is T(n) = 2*T(n/2) + O(n), which the Master Theorem handles cleanly (Case 2, giving Theta(n log n)). But its worst-case recurrence, when the pivot is consistently the smallest or largest element, is T(n) = T(n-1) + O(n), a subtractive recurrence the Master Theorem simply doesn't cover, resolved instead by direct summation to Theta(n^2). Knowing which recurrence actually describes the situation you're analysing, not just pattern-matching on "it's recursive so the Master Theorem must apply", is the real skill being tested whenever this topic comes up in an interview.

A quick reference table

Here is the entire theorem condensed into one table, worth bookmarking for quick lookups during an exam or an interview:

Keep this table next to any recursive algorithm you're analysing for the first time. In practice, the large majority of divide-and-conquer algorithms you'll encounter in standard coursework and interviews, merge sort, binary search, many matrix and tree algorithms, land cleanly in Case 1 or Case 2, and being able to identify a, b, and f(n) at a glance, then slot them into this table, is most of the actual work.

A habit worth building: whenever you meet a new recursive algorithm, write down its recurrence explicitly in the T(n) = a*T(n/b) + f(n) form before doing anything else, even before trying to guess which case it falls into. A surprising number of analysis mistakes come not from misapplying the theorem itself, but from mis-identifying a or b in the first place, for instance confusing "splits into two halves" (b=2) with "splits into two pieces of size n-1" (not of this form at all, and resolved differently, as the quicksort worst case above shows).

It's also worth remembering that the table above only lists the three cases, not the regularity condition attached to Case 3, or the precise log^k(n) bookkeeping inside Case 2. For the vast majority of recurrences you'll meet in coursework and interviews, that extra fine print never actually matters, f(n) is almost always a clean polynomial or polynomial-times-logarithm, and the regularity condition holds automatically. But if you ever meet an f(n) that oscillates, or grows unusually (not simply polynomial, not simply logarithmic), treat that as a signal to go back to first principles with a recursion-tree argument rather than trusting the table blindly.

Frequently Asked Questions