Why recursive code needs a recursive cost
By now you can count the cost of a loop: walk the body, see how many times it runs, multiply. But a recursive procedure refuses to be counted that way, because partway through its work it calls itself on a smaller input, and you do not yet know what that costs. The honest move is not to pretend, but to give the unknown a name. Let T(n) stand for the running time on an input of size n — the very thing we are trying to find — and then write down an equation that T must satisfy. That equation is a recurrence: a description of T(n) in terms of T of smaller arguments.
This is not circular cheating; it is the same trick as induction on the recursive calls that we used for correctness, now applied to cost. There we assumed the recursive call returned the right answer on smaller inputs and only checked the glue around it. Here we assume the recursive call takes exactly T(of its smaller size) and only count the extra work the current call does on its own. Solving the recurrence — the job of the next four guides — is what finally turns that named unknown into a clean Big-O.
Reading the equation straight off the code
There is a mechanical recipe, and it always has two parts. First, find every recursive call the procedure makes and note how big each call's input is — this gives the T(...) terms on the right-hand side. Second, count all the non-recursive work in one call: the partitioning, the merging, the comparisons, the loop that runs before or after the calls. That non-recursive work, written as a function of n, is usually called f(n). Glue them together and you have T(n) = (the call terms) + f(n). The whole skill of this section is keeping these two parts separate and not double-counting.
- Scan the body for self-calls. Count how many there are and the input size of each — e.g. two calls on halves, or one call on n-1.
- Add up the non-recursive work in this single call as a function of n; that is f(n) (often Theta(1), Theta(n), or Theta(n^2)).
- Write T(n) = (sum of T over the call sizes) + f(n) — the recursive case, valid only for n large enough.
- State the base case separately: pin down T at the smallest size where the code stops recursing, e.g. T(1) = Theta(1).
Run the recipe on merge sort. It makes two recursive calls, each on half the array, so the call terms are T(n/2) + T(n/2) = 2 T(n/2). The only non-recursive work is the linear-time merge of the two sorted halves, so f(n) = Theta(n). That yields the divide-and-conquer recurrence T(n) = 2 T(n/2) + Theta(n) — exactly the equation you met when we counted merge sort, now derived rather than handed to you. Binary search reads off just as cleanly: one call on half the array and Theta(1) work to pick the side, giving T(n) = T(n/2) + Theta(1).
The a, b, f(n) shape and where it breaks
Many divide-and-conquer algorithms produce a recurrence of one tidy shape, T(n) = a T(n/b) + f(n), and it pays to read the three knobs out loud. Here a is how many subproblems you create, b is the factor by which each subproblem shrinks, and f(n) is the work to split the input and combine the answers. Merge sort has a=2, b=2, f(n)=Theta(n). Karatsuba multiplication famously turns the naive a=4 into a=3 with b=2 and f(n)=Theta(n), and that single drop from 4 to 3 is the whole reason it beats grade-school multiplication. Recognizing a, b, f is what lets the master theorem fire.
T(n) = a * T(n/b) + f(n)
| | |
| | +--- work OUTSIDE the recursive calls (split + combine)
| +----------- each subproblem is 1/b the size
+-------------------- number of recursive calls
merge sort : a=2, b=2, f(n)=Theta(n)
binary search: a=1, b=2, f(n)=Theta(1)
Karatsuba : a=3, b=2, f(n)=Theta(n)Be honest, though: not every recursion fits this mould, and pretending otherwise is the most common beginner trap. Some algorithms split unevenly — quicksort, in the worst case, peels off one element and recurses on n-1, giving T(n) = T(n-1) + Theta(n), which is a decrease-by-one recurrence, not a divide-by-b one. Others split into pieces of different sizes, like T(n) = T(n/3) + T(2n/3) + Theta(n); these are the uneven-split recurrences that the plain master theorem simply cannot touch, and we will need the Akra-Bazzi method for them. Writing the recurrence correctly is what reveals which tool you are allowed to use.
Do not forget the base case
A recurrence with only its recursive line is a sentence with no full stop. The recursive case T(n) = 2 T(n/2) + Theta(n) describes large inputs, but it is meaningless until you say where the recursion bottoms out. That is the base case: the smallest input the code handles directly, almost always with constant work, written T(1) = Theta(1) (or T(n) = Theta(1) for n at or below some small threshold). Without it, T is genuinely undefined — and the recursion in the actual program would never stop.
Four ways to solve it — a map of the rung
Once the recurrence is written, the goal is a closed-form Big-O. There is no single button for this, and the four guides ahead are four genuinely different tools — worth previewing so you know what you are reaching for. The recursion-tree method draws the calls as a branching tree, computes the work on each level, and sums down the levels; it is the most visual and the best for building intuition about where the time goes. The substitution method is the rigorous backbone: you guess the answer and then prove it by induction, the only one of the four that yields an airtight proof rather than a confident estimate.
The third tool is the headline act. The master theorem is a lookup table for the shape T(n) = a T(n/b) + f(n): compare f(n) against the benchmark n raised to the critical exponent log base b of a, and one of three cases hands you the answer with no tree-drawing at all. It is fast and it covers a huge slice of divide-and-conquer algorithms — but be clear-eyed: it solves only that shape, it has fine print (a regularity condition in one case), and it deliberately ignores the rest. The fourth guide, Akra-Bazzi, is the generalization that rescues the uneven and many-term recurrences the master theorem leaves stranded.