What Is a Recurrence Relation? A Beginner's Guide

You write a recursive function. It calls itself twice. You stare at it and think "that's... exponential somehow, right?" You are correct. Then the interviewer asks you to prove it, and you discover that "somehow" doesn't really hold up under questioning.

Recurrence relations turn that vague instinct into a proof. A recurrence defines T(n), the running time on input size n, in terms of T of smaller inputs. The recurrence mirrors the recursion itself: two calls on half the input gives T(n) = 2T(n/2) + whatever-work-you-do-outside-those-calls.

Once you can write one, you can analyze any recursive algorithm on sight. In interviews, that's the difference between "O(n log n), I think" and "O(n log n), and here's why." The second answer impresses. The first one just goes in the pile.

A Recurrence Relation Is Just a Function That References Itself

A recurrence defines T(n) in terms of T of smaller values. That's it. Same structure as the recursion.

If a recursive function calls itself on a problem half the size and does O(n) work outside that call:

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

If it calls itself twice on half-size problems with O(1) outside work:

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

The recurrence mirrors the code. Read the function, count the recursive calls, measure the subproblem size, measure the outside work. Done.

The Recurrence Writes Itself (Once You Know Where to Look)

Three questions. That's the entire process.

Here's binary search:

def binary_search(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    else:
        return binary_search(arr, target, lo, mid - 1)

How many recursive calls? One.
What size is the subproblem? n/2.
What work happens outside the recursion? O(1).

Recurrence: T(n) = T(n/2) + O(1)

Now merge sort:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)  # O(n) to merge

Recursive calls? Two.
Subproblem size? n/2 each.
Outside work? O(n) to merge.

Recurrence: T(n) = 2T(n/2) + O(n)

One more. This one is going to hurt.

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Recursive calls? Two.
Subproblem sizes? n-1 and n-2.
Outside work? O(1).

Recurrence: T(n) = T(n-1) + T(n-2) + O(1)

Notice this one subtracts instead of divides. That changes everything. You'll see why in a moment.

Three Tools for Solving Recurrences

You have the recurrence. Now you need the actual complexity. Three tools handle everything you'll encounter in practice.

Tool 1: The Master Theorem

The Master Theorem solves any recurrence of the form T(n) = aT(n/b) + f(n) where a ≥ 1 and b > 1. This covers virtually every divide-and-conquer algorithm.

The theorem compares f(n) against n^(log_b a), which represents the work done at the leaves of the recursion tree.

Case	Condition	Result
Leaf-heavy	f(n) = O(n^c) where c < log_b(a)	T(n) = Θ(n^(log_b a))
Balanced	f(n) = Θ(n^(log_b a))	T(n) = Θ(n^(log_b a) · log n)
Root-heavy	f(n) = Ω(n^c) where c > log_b(a)	T(n) = Θ(f(n))

Applied to binary search: a=1, b=2, f(n)=O(1). log_2(1) = 0, so f(n) = Θ(n^0) = Θ(1). Balanced case. T(n) = Θ(log n).

Applied to merge sort: a=2, b=2, f(n)=O(n). log_2(2) = 1, so f(n) = Θ(n^1). Balanced case again. T(n) = Θ(n log n).

The Master Theorem cannot help with Fibonacci. Subproblems that shrink by subtraction (n-1, n-2) don't fit the T(n/b) form. You need a different tool.

Tool 2: Unrolling

When the Master Theorem doesn't apply, expand the recurrence manually until a pattern appears.

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

T(n) = T(n-1) + 1
     = T(n-2) + 1 + 1
     = T(n-3) + 1 + 1 + 1
     = T(n-k) + k

At k=n, T(0) = 1. So T(n) = n + 1 = O(n).

For Fibonacci's T(n) = T(n-1) + T(n-2) + 1, unrolling gets messy fast. Notice instead that T(n-2) ≥ T(n-1)/2, so T(n) ≥ 2·T(n-2). That's doubling with halving steps: O(2^(n/2)) as a lower bound. A tighter bound via the characteristic equation gives O(φⁿ) where φ ≈ 1.618. In interviews, O(2^n) is the accepted answer.

O(2^n) means what you think it means.

Finding the 87th Fibonacci number using recursion with no memoization on a computer capable of 1 billion operations per second, Interstellar "this little maneuver is gonna cost us 51 years" meme

fib(87) with no memoization. Your laptop's fans will spin up first.

Tool 3: The Recursion Tree

Draw the recursion as a tree. Each node is a subproblem. Sum the work across each level.

For T(n) = 2T(n/2) + O(n):

Recursion tree diagram for merge sort showing T(n) splitting into T(n/2) at each level with O(n) work per level across log n total levels equaling O(n log n)

Level 0: one problem of size n, doing O(n) work
Level 1: two problems of size n/2, each O(n/2) → O(n) total
Level 2: four problems of size n/4, each O(n/4) → O(n) total
Level log n: n problems of size 1, O(1) each → O(n) total

O(log n) levels, O(n) work each. Total: O(n log n).

When work per level is constant, you're in the balanced case. When it grows toward the leaves, the leaves dominate. When it shrinks toward the root, the root dominates. Memorize this and you'll often recognize complexity on sight without doing the full algebra.

A quick guide on which tool to reach for first:

Master Theorem first. If your recurrence is T(n) = aT(n/b) + f(n), plug in a and b and check the three cases. Most divide-and-conquer algorithms land here.
Unrolling when subproblems shrink by subtraction. Any T(n-1), T(n-2), or T(n-k) recurrence won't fit the Master Theorem. Expand until the pattern appears.
Recursion tree for understanding. Even when you use the Master Theorem, drawing the tree tells you why the answer is what it is. That's the part interviewers actually want to hear.

The Space Recurrence: Often Ignored, Always Asked

Stack depth follows its own recurrence. For binary search:

S(n) = S(n/2) + O(1)

This solves to O(log n). Every recursive call adds one frame; the deepest chain determines total space.

For merge sort, the call stack goes log n levels deep before bottoming out: O(log n) for the stack, plus O(n) for the temporary arrays. Both matter. When someone asks for your space complexity, they almost always mean auxiliary space, so know which version you're analyzing.

For naive Fibonacci:

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

The deepest chain is fib(n) → fib(n-1) → fib(n-2) → ... → fib(1). That's O(n) stack space even though the tree has O(2^n) total nodes.

Call stack space is the deepest path, not the total number of calls.

This trips people up every time. The time complexity is exponential. The space complexity is linear. They're measuring different things, which is exactly why you need to write the recurrences separately.

What Interviewers Are Actually Testing

Interviewers don't ask you to formally derive recurrences on a whiteboard. They ask you to explain complexity, then probe whether you understand why.

"Why is merge sort O(n log n)?"

Option one: "Because that's what I memorized." Gets a polite nod and nothing else.

Option two: "It makes two recursive calls on n/2 elements, then merges in O(n). That gives T(n) = 2T(n/2) + O(n). The merge cost is constant across all log n levels of the recursion tree, so the total is O(n log n)."

The second answer works for algorithms you've never seen, because you're deriving, not recalling.

Tweet from @byte_thrasher: first programming interview, asked about time complexity, answered "not that complex", 165K views

Everyone starts here. The gap to close is smaller than it looks.

Form the recurrence as soon as you write a recursive solution:

Count recursive calls (a)
Identify subproblem size (n/b or n-k)
Identify outside work (f(n))
Write T(n) = aT(n/b) + f(n) or T(n) = T(n-k) + f(n)
Apply the Master Theorem or unroll

For common patterns, you'll recognize the answer before finishing the algebra:

One call, half the problem, O(1) outside → O(log n)
Two calls, half the problem, O(n) outside → O(n log n)
Two calls, same-minus-one problem, O(1) outside → O(2^n)
One call, same-minus-one problem, O(n) outside → O(n²)

That last one trips people up. It's the naive string concatenation pattern, or any recursion that scans the remaining input on every call.

Memoization Breaks the Recurrence

Naive Fibonacci is O(2^n). Add memoization and each of the n distinct subproblems is computed exactly once. The recurrence changes completely:

Without memoization: T(n) = T(n-1) + T(n-2) + O(1) = O(2^n)
With memoization:    T(n) = n states × O(1) per state = O(n)

Memoization converts the recursion tree into a DAG, collapsing all the redundant paths. The analysis for memoized DP isn't a traditional recurrence at all. It's a state-space argument: count states, multiply by work per state.

This is why DP complexity analysis feels different from divide-and-conquer. You're answering the same question. Just from a different angle.

If you're preparing for coding interviews, SpaceComplexity lets you practice explaining this reasoning out loud under realistic interview pressure. Knowing the theory is step one. Narrating it clearly on demand is a different skill.