Recurrence Relations

Counting the work in a loop is straightforward: you find how many times the body runs and multiply. But a recursive algorithm is defined in terms of itself, so its cost is too. Merge sort sorts a list of n items by sorting two halves — and the cost of sorting a half is just "the same problem, smaller." How long does the whole thing take? The honest first answer is a sentence that refers to itself: "the time for n is twice the time for n/2, plus the cost of merging."

That self-referential sentence, written as an equation, is a recurrence relation. It is the bridge between recursive code and a closed-form running time like \Theta(n\log n). This page is about the first half of that bridge — reading a recurrence off the code faithfully. Solving it (recursion trees, the master theorem) comes after; get the recurrence wrong and every clever solving technique gives you a confident wrong answer.

From recursive code to a recurrence

Let T(n) stand for the number of basic operations the algorithm performs on an input of size n. To write the recurrence, read the function body and add up three kinds of cost:

The recursive calls — for each call the function makes on itself, add a T(\cdot) term with that call's input size inside. Two calls on half the input contribute 2\,T(n/2).
The non-recursive work — everything else this call does before, between, and after the recursive calls (splitting, combining, a loop over the input): a function f(n), often \Theta(1) or \Theta(n).
The base case — the size at which recursion stops, and its (constant) cost. Every recurrence needs a base case: T(1) = \Theta(1). Without it the equation describes an infinite regress, not an algorithm.

Consider binary search. It looks at the middle element in \Theta(1) time, then recurses into one half:

function binarySearch(a: number[], target: number, lo: number, hi: number): number { if (lo > hi) return -1; // base case: empty range, O(1) const mid = (lo + hi) >> 1; // O(1) work if (a[mid] === target) return mid; // O(1) if (a[mid] < target) return binarySearch(a, target, mid + 1, hi); // ONE recursive call, half the range else return binarySearch(a, target, lo, mid - 1); // ONE recursive call, half the range }

One recursive call on half the input, a constant amount of work around it. That reads directly off the code as

T(n) = T(n/2) + \Theta(1), \qquad T(1) = \Theta(1).

Notice we wrote T(n/2), not 2\,T(n/2) — binary search throws away the half it doesn't enter. That single-vs-double distinction is exactly what separates \Theta(\log n) from \Theta(n), so it is worth getting right.

The divide-and-conquer template

Most recurrences you meet come from divide-and-conquer algorithms, and they all share one shape. A problem of size n is broken into a subproblems, each of size n/b, with f(n) work to divide and to combine:

T(n) = a\,T(n/b) + f(n), \qquad a \ge 1,\; b > 1.

Read the three knobs straight off the algorithm:

Knob	Meaning	Merge sort
a	how many subproblems you recurse on	2 (both halves)
b	the factor by which the size shrinks	2 (each half is n/2)
f(n)	divide + combine work outside the calls	\Theta(n) (the merge)

Crucially a and b are independent. Binary search has a = 1, b = 2 (shrink by half, but only one child). Merge sort has a = 2, b = 2 (shrink by half, and two children). Same b, wildly different cost — because a controls how fast the number of subproblems multiplies as you descend.

The picture above is merge sort's call tree on n = 8: the root problem of size 8 spawns two of size 4, each of those spawns two of size 2, and so on. With a = 2 the tree branches; the number of nodes on level i is a^i = 2^i, and the depth is \log_b n = \log_2 8 = 3. Every recurrence hides a tree like this, and the tree is what we will sum when we solve it.

Three recurrences to keep in your pocket

A handful of recurrences show up everywhere. Learn to recognise them by the shape of the recursion, not by memorising answers:

Linear recursion — T(n) = T(n-1) + \Theta(1). One call on an input just one smaller (not a fraction), constant work each. Think: computing n! recursively, or the length of a linked list. It unrolls into n constant steps, so T(n) = \Theta(n).
Halving, one child — T(n) = T(n/2) + \Theta(1). Binary search. The size halves each step, so there are only \log_2 n steps: T(n) = \Theta(\log n).
Halving, two children, linear glue — T(n) = 2\,T(n/2) + \Theta(n). Merge sort. Each of \log n levels does \Theta(n) total work, giving T(n) = \Theta(n\log n).

Stare at the first two: T(n-1) + \Theta(1) and T(n/2) + \Theta(1) do the same constant work per call, yet the first is \Theta(n) and the second \Theta(\log n). The difference is how the size shrinks: subtracting 1 gives n steps; dividing by 2 gives \log n steps. Whether you subtract or divide is the single most important feature of a recurrence.

If n = 7, the "two halves" are really 3 and 4, so an honest recurrence is T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + \Theta(n), ceilings and floors and all. It turns out this fuss almost never changes the asymptotic answer: for the well-behaved f(n) that show up in practice, the floors and ceilings shift the solution by only a constant factor, which \Theta(\cdot) swallows whole. So by universal convention we write the clean T(n/2) and quietly assume n is a power of b — the rigorous version (via the Akra–Bazzi method) confirms the shortcut is safe. Drop the floors when solving; put them back only if a picky proof demands it.

The commonest mistake is writing 2\,T(n/2) for binary search because you see two recursive calls in the code. But look again: they sit in the two branches of an if/else — exactly one of them runs on any given execution. The recurrence counts the calls a single run makes, so it is T(n/2), not 2\,T(n/2). The mirror mistake is undercounting: a function that calls itself twice on the same subproblem (naïve recursive Fibonacci) really is T(n) = T(n-1) + T(n-2) + \Theta(1), and both calls run — that recurrence is exponential, not linear. Trace one concrete execution and tally the calls it makes; don't just grep the source for the function name.

Unrolling: a sanity check before the heavy machinery

You can often see the answer by expanding a recurrence a few times and spotting the pattern — a method called unrolling (or iteration). Take the linear recurrence T(n) = T(n-1) + c:

T(n) = T(n-1) + c = T(n-2) + 2c = \dots = T(1) + (n-1)c = \Theta(n).

Each step peels off one c and drops n by one, so after n-1 steps we hit the base case having accumulated (n-1)c. Do the same for T(n) = T(n/2) + c and the size halves each step, so you reach the base after only \log_2 n steps: T(n) = c\log_2 n + T(1) = \Theta(\log n). Unrolling is informal but priceless — it tells you what answer the rigorous methods should produce, so you notice when you have misread the recurrence.