The first time someone asked me to derive the time complexity of merge sort from a recurrence relation, I bluffed. I had memorised that merge sort is O(n log n) and figured the deriving part was a formality nobody actually did. Then in a code review three years later I argued that a divide-and-conquer function I had written was O(n) and a colleague quietly produced a recurrence that proved it was O(n log n). I had been confidently wrong about my own code. That was the day I sat down and learned to write recurrences properly, and I have never had a confident-but-wrong moment about a recursive algorithm since.

Recurrences are how you talk about the cost of a recursive function in a way that is actually checkable. Time complexity by inspection is fine for a single loop. The moment a function calls itself, especially more than once, inspection lies. The recurrence does not.

This article is the explanation I wish I had read before that code review. No formal mathematics, no calculus, just enough to derive the cost of any reasonable divide-and-conquer function in about two minutes.

What a recurrence actually is

A recurrence relation describes the cost T(n) of a function in terms of the cost on smaller inputs. That is the whole definition. If your function does some constant-time work and then calls itself once on input of size n - 1, the recurrence is:

T(n) = T(n - 1) + O(1)

Read that as a contract: the cost of solving size n equals the cost of solving size n - 1 plus a constant. There is also a base case, usually T(1) = O(1), that says small inputs are constant cost.

If your function does O(n) work and then makes two recursive calls on input of size n / 2 (the merge-sort shape), the recurrence is:

T(n) = 2 * T(n / 2) + O(n)

Two subproblems, each half the size, plus linear work to combine. That is the line that I would have written down in the code review I lost, and it is the line that immediately tells you the answer is O(n log n).

The structure of every recurrence has three parts: how many recursive calls (the branching factor), how much smaller the input gets per call (the shrink rate), and how much non-recursive work happens per call. Get those three numbers right and the recurrence writes itself.

The four shapes that cover ninety percent of code

In production I have basically only ever seen four recurrences. If you can recognise these on sight, you will rarely need to grind through the math.

Three other shapes show up occasionally and are worth knowing.

T(n) = T(n / 2) + O(n)        ->  O(n)         e.g. linear-time selection in a balanced split
T(n) = 2 * T(n - 1) + O(1)    ->  O(2^n)       e.g. naive subset / power set generation
T(n) = T(n - 1) + T(n - 2)    ->  O(phi^n)     naive Fibonacci, golden-ratio exponent

That last one is the bug everyone writes once. Naive Fibonacci is exponential. Memoised Fibonacci collapses to O(n), because each subproblem is now solved exactly once. The recurrence changes from T(n) = T(n - 1) + T(n - 2) to "you compute T(0) through T(n) in order, each in O(1) given the previous two". The cost of the algorithm changes by an entire complexity class because the recurrence changes.

The recursion tree, in plain pictures

When I cannot recognise the recurrence on sight, I draw the recursion tree. Two minutes with a pen on paper beats fifteen minutes of staring at the source code.

For T(n) = 2 * T(n / 2) + O(n), the tree looks like this:

Recursion tree for T(n) = 2T(n/2) + O(n)
                T(n)              -> n work
              /      \
           T(n/2)   T(n/2)        -> n/2 + n/2 = n work
          /   \     /    \
       T(n/4) T(n/4) T(n/4) T(n/4) -> 4 * n/4 = n work
        ...

Each level of the tree does O(n) total work. The tree has log n levels (you halve until you hit 1). Total work: O(n log n). The picture is the proof.

For T(n) = T(n / 2) + O(n), the tree degenerates into a chain, and the work per level halves.

T(n)         -> n
T(n/2)       -> n/2
T(n/4)       -> n/4
...
T(1)         -> 1

Sum of a geometric series: n + n/2 + n/4 + ... <= 2n. So this recurrence is O(n), not O(n log n). Same number of levels as merge sort, very different total work because the per-level cost shrinks geometrically.

The general lesson from the tree picture: if work-per-level is constant across levels, the answer is levels * work-per-level. If work-per-level shrinks geometrically (each level half the previous), the sum is dominated by the root and the answer is O(work-at-root). If work-per-level grows geometrically toward the leaves, the answer is dominated by the leaves and you count them.

Worked example: from code to recurrence to bound

Here is a real function I had to analyse last quarter. It computes the maximum sum of a subarray, divide-and-conquer style.

def max_subarray(arr, lo, hi):
    if lo == hi:
        return arr[lo]
    mid = (lo + hi) // 2
    left_best = max_subarray(arr, lo, mid)
    right_best = max_subarray(arr, mid + 1, hi)
    cross_best = max_crossing(arr, lo, mid, hi)   # O(n) scan around mid
    return max(left_best, right_best, cross_best)

Let n = hi - lo + 1. Two recursive calls on halves, plus one O(n) max_crossing. The recurrence is:

T(n) = 2 * T(n / 2) + O(n)

The merge-sort shape. So O(n log n). That answer is one row from the table above; I do not need to derive anything.

The reason this matters is that there is a faster solution (Kadane's algorithm) that solves the same problem in O(n) linear time. If you only know your divide-and-conquer is "fast", you might ship it. The recurrence forces you to compare n log n against n, and at that point you know to look for the linear version before code review forces you to.

Recurrences for code that does not look recursive

The recurrence trick also works on iterative code that has the same divide-and-conquer shape. Binary search is the obvious example.

def bsearch(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

There is no recursive call, but each iteration halves the search range and does O(1) comparisons. If you imagined writing the recursive version, the recurrence would be T(n) = T(n / 2) + O(1), which is O(log n). The iterative version has the same cost; the loop is just a different way of expressing the recursion.

The same trick reveals that for i in range(n): for j in range(i): ... is O(n^2), because the recurrence of "how much work does the outer loop do at size n" is T(n) = T(n - 1) + O(n), which sums to n^2. Iterative or recursive does not change the underlying shape; the recurrence is the algorithm's signature.

Two recurrence pitfalls I have personally fallen into

The first pitfall is forgetting to count work in the combine step. When I write a divide-and-conquer that "splits, recurses, and concatenates the result lists", the concatenation is not free. If each result list can be size n / 2, the concatenation is O(n), and that turns what looked like a T(n) = 2 * T(n / 2) + O(1) recurrence (which would be O(n)) into T(n) = 2 * T(n / 2) + O(n) (which is O(n log n)). The shape of the function did not change, only my honest accounting of the combine cost. Off by one complexity class because of one missed line.

The second pitfall is recursing on a non-fixed fraction of the input. If the recurrence is T(n) = T(n - 1) + O(n), that is O(n^2). If I think the recursive call shrinks the problem more than it actually does (say, my code drops one element off the front when I thought it dropped half), I will write T(n) = T(n / 2) + O(n) on the whiteboard, conclude O(n), and ship something quadratic. The fix is to read my own code carefully and confirm what the recursive call actually receives, not what I intended it to receive.

Sketch the recurrence before you write the code

The lesson I took from getting publicly corrected on a recurrence is to flip the order of operations. I now write the recurrence on a notepad before I write the function. If the shape is 2 * T(n / 2) + O(n), I know I am committing to O(n log n) and I check whether that is acceptable for the input size we expect. If it is not, I rework the algorithm before any code lands. Treating recurrences as an after-the-fact analysis tool was what got me into trouble; treating them as a design tool is what stopped me from getting into it again. The math here is genuinely small, the four shapes in the table cover most of what real code does, and the time saved by spotting O(2^n) on the whiteboard rather than at three in the morning during an incident is worth the ninety seconds it takes to sketch the tree.