When you analyze a recursive algorithm, the running time isn't obvious by looking at it. A function that calls itself doesn't have a simple loop count you can read off the page.

But there is a pattern to lean on: the cost of solving a problem of size n is written in terms of the cost of the smaller subproblems it calls. That self-referential definition is exactly what a recurrence relation captures.

A recurrence relation expresses a sequence or function in terms of its own earlier values.

Put plainly:

A recurrence relation tells you how to compute the next value from the ones that came before it.

The classic Fibonacci sequence is a clean example:

Each number is the sum of the two before it.

That rule can be expressed mathematically as: F(n) = F(n−1) + F(n−2)

with base cases: F(0) = 0, F(1) = 1

That formula is a recurrence relation. It defines each term using the terms before it, and that is the same idea we use to analyze the running time of recursive algorithms.

When you write a recursive function, each call does some work of its own and then hands the rest off to calls on smaller inputs. That structure translates directly into a recurrence relation.

Take merge sort, for instance:

Reading it piece by piece:

This recurrence captures how the total time T(n) depends on the cost of its subproblems. Solving it gives the familiar O(n log n).

A recurrence relation, then, is just recursion written as a cost equation.

A recurrence relation generally looks like this:

Where:

A few common algorithms and their recurrences:

The quick sort row needs a caveat. T(n) = 2T(n/2) + O(n) is quick sort's best case, where every partition splits the array evenly. Its average case is also O(n log n), but the recurrence is different: the pivot lands at a random position, so the analysis averages the cost over all possible split points rather than assuming a clean halving. And when partitions are maximally unbalanced, quick sort degrades to T(n) = T(n−1) + O(n), which is O(n²).

A recursion tree is the clearest way to see where the time goes. Let’s draw one for merge sort’s recurrence T(n) = 2T(n/2) + n. Each node is a call, and it branches into the two half-size calls it makes:

The key observation is that the work at each level of the tree adds up to n. The top level does n work in one call. The next level has two calls doing n/2 each, which is n again. The level below has four calls doing n/4 each, still n. Halving the size while doubling the number of calls keeps the per-level total constant.

Since each call halves the input, the tree is log n levels deep. Multiply the per-level work by the number of levels and you get n × log n, which is the O(n log n) we expected.

Writing a recurrence is only half the job. Solving it is what turns T(n) = 2T(n/2) + n into a Big O you can actually compare against other algorithms.

There are four techniques worth knowing, roughly in order of how often they come up:

We'll work through the first three here, and the master theorem gets its own chapter next.

This is the most direct method. You guess the answer, based on a similar recurrence or the shape of the problem, then prove the guess is correct using mathematical induction.

Given the recurrence: T(n) = 2T(n/2) + n

Step 1. Guess the solution

We suspect T(n) = O(n log n), because we halve the problem and recurse on both halves, then do linear work to merge.

Step 2. Prove it by induction

We want to show that T(n) ≤ c·n·log n for some constant c and all n past a starting point.

Base case:

We anchor the induction at n = 2 rather than n = 1. At n = 1 the bound c·n·log n collapses to c·1·log 1 = 0, but T(1) is a positive constant, so the bound can't hold there. At n = 2, T(2) is a constant and c·2·log 2 = 2c, so we can pick c large enough that T(2) ≤ 2c holds.

Inductive step:

Assume the bound holds for all smaller sizes, in particular for n/2. Starting from the recurrence:

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

Substitute the inductive hypothesis:

For any c > 1, the term n(c − 1) is positive, so T(n) ≤ c·n·log n − n(c − 1) ≤ c·n·log n. The bound holds, which confirms T(n) = O(n log n).

Instead of guessing, the recursion tree method unfolds the recurrence into a tree and adds up the work done at each level. It's the method behind the visualization we drew earlier, made systematic.

Take merge sort again: T(n) = 2T(n/2) + n. Laying out the work level by level:

Every level sums to n, and the tree is log n levels deep because the input keeps halving until it reaches size 1. The total is the per-level work times the number of levels:

This method is especially useful when f(n) isn't constant across levels, because you can see exactly how the work is distributed instead of having to guess a closed form.

When a recurrence shrinks by subtraction rather than division (so the recursion tree degenerates into a single chain), the cleanest approach is to expand it by hand until a pattern appears, then sum the series.

Take T(n) = T(n−1) + n:

The leftover terms form an arithmetic series. Since 1 + 2 + 3 + ... + n = n(n+1)/2, the whole sum grows like n²/2, which is O(n²). This is exactly the recurrence for an unbalanced quick sort, which is why its worst case is quadratic.

For the common divide-and-conquer shape T(n) = aT(n/b) + f(n), you don't need substitution, a recursion tree, or manual expansion at all. The Master Theorem reads the answer straight off the values of a, b, and f(n).

It's the fastest way to solve most divide-and-conquer recurrences, and it's important enough to get its own chapter.

Substitution, recursion trees, and iterative expansion will carry you through almost any recurrence you need to analyze by hand. But for that one extremely common shape, T(n) = aT(n/b) + f(n), there's a direct formula that skips the work entirely.

That formula is the Master Theorem, which we'll cover in the next chapter.