Merge sort, binary search, and most “divide and conquer” algorithms all share one shape: split the problem, solve the pieces recursively, combine the results. A recurrence relation captures that shape as an equation, and solving it tells you the Big-O without simulating a single run.

What you’ll learn

• What a recurrence relation is and where it comes from.
• The recursion tree method — solving a recurrence by hand, level by level.
• The Master Theorem and its three cases.
• How merge sort and binary search reduce to closed-form Big-O.
• A small simulator that computes recurrence cost numerically.

Where a recurrence comes from

A divide-and-conquer algorithm that splits an input of size $n$ into $a$ subproblems of size $n/b$, then spends $f(n)$ extra work combining the results, has total cost:

• $a$ — how many subproblems you recurse into.
• $b$ — how much smaller each subproblem is ($n$ shrinks to $n/b$).
• $f(n)$ — the work done outside the recursive calls (splitting + combining).

Merge sort, for example, splits into 2 halves ($a = 2$, $b = 2$) and spends $O(n)$ merging them back together — giving $T(n) = 2T(n/2) + O(n)$.

The recursion tree method

Draw the recursion as a tree: the root does $f(n)$ work, its $a$ children each do $f(n/b)$ work, their children do $f(n/b^2)$, and so on until subproblems hit the base case. Summing every level’s cost gives the total.

  graph TD
    A["T(n)
merge cost: n"] --> B["T(n/2)
merge cost: n/2"]
    A --> C["T(n/2)
merge cost: n/2"]
    B --> D["T(n/4)
cost: n/4"]
    B --> E["T(n/4)
cost: n/4"]
    C --> F["T(n/4)
cost: n/4"]
    C --> G["T(n/4)
cost: n/4"]

Every level’s costs add up to roughly $n$ (the halves sum back to the whole), and there are $\log_2 n$ levels before subproblems reach size 1. So total cost is $n \cdot \log_2 n = O(n \log n)$ — no need to draw the whole tree once you see the pattern.

The Master Theorem

Drawing a tree every time is tedious. The Master Theorem gives a direct answer for $T(n) = aT(n/b) + f(n)$ (with $a \ge 1$, $b > 1$) by comparing $f(n)$ to $n^{\log_b a}$ — the cost if there were no extra work at all:

In plain language: if the combine step is smaller than the recursive work, the recursion dominates (Case 1). If they’re equal, add a $\log n$ factor (Case 2). If the combine step dominates, the top level alone sets the cost (Case 3).

  graph TD
    A["Compare f(n) to n^(log_b a)"] --> B{"Is f(n) polynomially smaller?"}
    B -- Yes --> C["Case 1
T(n) = Theta(n^(log_b a))"]
    B -- No --> D{"Is f(n) equal (same order)?"}
    D -- Yes --> E["Case 2
T(n) = Theta(n^(log_b a) * log n)"]
    D -- No --> F{"Is f(n) polynomially larger
+ regularity condition holds?"}
    F -- Yes --> G["Case 3
T(n) = Theta(f(n))"]

Worked examples

Merge sort: $T(n) = 2T(n/2) + O(n)$. Here $a = 2$, $b = 2$, so $\log_b a = \log_2 2 = 1$, and $f(n) = O(n^1)$ — the same order. That’s Case 2, so:

Binary search: $T(n) = T(n/2) + O(1)$. Here $a = 1$, $b = 2$, so $\log_b a = \log_2 1 = 0$, and $f(n) = O(n^0) = O(1)$ — again the same order. Also Case 2, giving:

A recurrence-cost simulator

Instead of drawing trees by hand, you can compute $T(n)$ numerically by literally implementing the recurrence, and compare it to the closed-form prediction:

def recurrence_cost(n, a, b, f, base=1):
    """Numerically evaluate T(n) = a * T(n // b) + f(n)."""
    if n <= base:
        return 1
    return a * recurrence_cost(n // b, a, b, f, base) + f(n)
 
n = 64
 
# Merge sort: T(n) = 2T(n/2) + n  ->  should track n * log2(n)
merge_cost = recurrence_cost(n, a=2, b=2, f=lambda n: n)
print("merge sort cost:  ", merge_cost, " ~ n log n =", n * n.bit_length())
 
# Binary search: T(n) = T(n/2) + 1  ->  should track log2(n)
search_cost = recurrence_cost(n, a=1, b=2, f=lambda n: 1)
print("binary search cost:", search_cost, " ~ log n =", n.bit_length() - 1)

def recurrence_cost(n, a, b, f, base=1):
    """Numerically evaluate T(n) = a * T(n // b) + f(n)."""
    if n <= base:
        return 1
    return a * recurrence_cost(n // b, a, b, f, base) + f(n)
 
n = 64
 
# Merge sort: T(n) = 2T(n/2) + n  ->  should track n * log2(n)
merge_cost = recurrence_cost(n, a=2, b=2, f=lambda n: n)
print("merge sort cost:  ", merge_cost, " ~ n log n =", n * n.bit_length())
 
# Binary search: T(n) = T(n/2) + 1  ->  should track log2(n)
search_cost = recurrence_cost(n, a=1, b=2, f=lambda n: 1)
print("binary search cost:", search_cost, " ~ log n =", n.bit_length() - 1)

Practice

Drill 1 — the critical exponent. $\log_b a$ is the exponent every Master Theorem case compares against. Compute it with math.log(a, b)math.log(a, b).

Drill 2 — simulate the recurrence. Finish the recursive call so the simulator actually recurses on the smaller subproblem.

Drill 3 — pick the Master Theorem case. Given the critical exponent and $f(n)$’s exponent, decide which case applies.

Recap

• Divide-and-conquer cost is captured by $T(n) = aT(n/b) + f(n)$.
• The recursion tree method sums cost per level; number of levels is $\log_b n$.
• The Master Theorem gives the closed form directly by comparing $f(n)$ to $n^{\log_b a}$ — no tree required.
• Merge sort: $\Theta(n \log n)$. Binary search: $\Theta(\log n)$. Both land in Case 2.

Next: Space Complexity and the Call Stack — what recursion actually costs in memory, not just time.