Recurrence Relation Method

Recurrence Relation Method

When a function calls itself, its running time is defined in terms of itself. That circularity is the whole difficulty: you can't just count a loop, because the "loop body" is another copy of the same problem on smaller input. The recurrence relation method is the technique for writing that self-reference down as an equation and then unrolling it into a closed-form Big-O. Think of it as reading a recursive function's cost the way the function actually runs: do a little work here, then spawn smaller versions of yourself, and add up everything across all the levels of that spawning.

Precise definition

A recurrence relation expresses T(n), the cost on input size n, using T evaluated at smaller sizes, plus the non-recursive work done at this call. The two ingredients are always:

• The recursive term — how many subproblems and how big. Written a·T(n/b) (divide-and-conquer, e.g. 2T(n/2)) or T(n-k) (decrease-and-conquer, e.g. T(n-1)).
• The local work f(n) — everything the call does outside the recursive calls: partitioning, merging, a single comparison, a loop.
• A base case — T(0) or T(1) = O(1), where recursion stops. Without it the equation has no anchor and no solution.

So a full recurrence looks like T(n) = 2T(n/2) + O(n) with T(1) = O(1). Solving it means finding a non-recursive formula for T(n) and reporting its growth rate.

Worked example: merge sort, counted exactly

Merge sort splits an array in half, sorts each half recursively, then merges. Merging n elements costs about n comparisons/moves, so:

T(n) = 2T(n/2) + n,   T(1) = 0.

Solve by unrolling (repeated substitution). Take n = 8:

• Level 0: one problem of size 8 → merge work = 8.
• Level 1: two problems of size 4 → merge work = 2×4 = 8.
• Level 2: four problems of size 2 → merge work = 4×2 = 8.
• Level 3: eight problems of size 1 → base case, work = 0.

Every non-leaf level does exactly n = 8 units of work. The number of levels is log₂8 = 3. Total = 8 × 3 = 24, and in general T(n) = n·log₂n, i.e. O(n log n). The pattern is the key insight: total cost = (work per level) × (number of levels), and the number of levels is how many times you divide n down to 1.

Three canonical shapes to recognise on sight

• T(n) = T(n-1) + O(1) → O(n). One shrinking call, constant local work: linear recursion (sum a list). n levels, O(1) each.
• T(n) = T(n-1) + O(n) → O(n²). Levels do n, n-1, …, 1 work — an arithmetic series summing to n(n+1)/2 (e.g. naive quadratic selection).
• T(n) = 2T(n-1) + O(1) → O(2ⁿ). Branching factor 2 with depth n doubles the node count each level (Towers of Hanoi, subset enumeration). Naive Fibonacci is the looser shape T(n) = T(n-1) + T(n-2) + O(1) — bounded above by 2T(n-1), but its tight growth is Θ(φⁿ) ≈ Θ(1.618ⁿ), not 2ⁿ. Contrast this sharply with 2T(n/2), which only has log n levels — halving the input is worlds apart from decrementing it.

For divide-and-conquer T(n)=aT(n/b)+O(n⁽), the Master Theorem is the shortcut: compare n⁽ against n^(log_b a). Larger exponent wins; a tie adds a log n factor. Merge sort is the tie case (log₂2 = 1 = c) → O(n log n).

Pitfalls interviewers probe

• Forgetting the base case makes the recurrence meaningless — and in code, an infinite recursion / stack overflow. They will ask "what stops it?"
• Miscounting local work. If each call does a linear scan, the term is +O(n), not +O(1). Quicksort's partition is O(n); that single fact drives its whole analysis.
• Confusing branch count with depth. 2T(n/2) and 2T(n-1) both "call twice," but one is n log n and the other exponential. Interviewers love this trap.
• Ignoring the recursion-stack space cost. Even an O(n)-time linear recursion uses O(n) stack space; balanced divide-and-conquer uses O(log n) depth.
• Unbalanced splits. Quicksort's worst case is a pivot that splits n-1/0, giving T(n)=T(n-1)+O(n) = O(n²); balanced splits give the O(n log n) average. Same code, different recurrence.

When it matters + trade-offs

The recurrence method is how you predict an algorithm's class before coding it, and how you justify a design choice. Its practical payoff is seeing the boundary between complexity classes: memoising naive Fibonacci (T(n-1)+T(n-2)+O(1), tight Θ(φⁿ)) makes every subproblem compute once, collapsing exponential growth to O(n) — the entire point of dynamic programming is rewriting a bad recurrence into a good one. It also exposes the best/worst/average gap: quicksort is O(n log n) average but O(n²) worst, so we randomise the pivot to make the balanced recurrence overwhelmingly likely.

Trade-off vs neighbours: an O(n log n) divide-and-conquer sort beats an O(n²) one massively at scale, but the recursion carries constant-factor and O(log n) stack overhead — for tiny n, an O(n²) insertion sort with no call overhead actually wins, which is why real sort libraries switch to it below a threshold.

Key takeaways

• A recurrence = recursive term + local work + base case; solve it as (work per level) × (number of levels), which the recursion tree makes visible.
• Halving the input gives log n levels; decrementing gives n levels — so 2T(n/2)+n is O(n log n) but 2T(n-1) is O(2ⁿ). Never confuse branch count with depth.
• Use the Master Theorem as a shortcut for aT(n/b)+O(n⁽): compare c to log_b a; the tie case adds a log n factor.
• Recurrences reveal the best/worst/average gap and the DP payoff — rewriting a branching recurrence into a linear one is the core optimisation move.