Recurrence Relations

A recurrence relation is an equation that defines a function T(n) in terms of its values on smaller inputs — typically the running-time function of a recursive algorithm, written T(n) = ...T(smaller)... + extra work. Setting up the right recurrence from code is the first half of the analysis; solving it (finding a closed-form T(n) = Θ(...)) is the second half. There are three standard solution methods — substitution (guess and verify by induction), recursion tree (sum work level by level), and the Master Theorem (closed-form recipe for divide-and-conquer shape) — plus the Akra–Bazzi method for unbalanced splits.

1. Intuition — A Recurrence Is Just Recursion Written as Math

When you write a recursive function, you implicitly define a cost function T(n) that captures the running time on input of size n. The function recurses on smaller inputs, then does some extra work to combine the results. So:

T(n) = (cost of recursive sub-calls) + (cost of extra work at this level)

The shape of the recurrence mirrors the shape of the code. If your code makes 2 recursive calls each on half the input and does linear post-processing, the recurrence is T(n) = 2 · T(n/2) + Θ(n). If it makes 1 recursive call on n − 1 and does constant post-processing, the recurrence is T(n) = T(n − 1) + Θ(1). The recurrence is a literal translation of the recursion structure into a function equation.

To convert a recurrence to a closed-form running time (Θ of some explicit function), we need techniques that depend on the recurrence’s shape:

• Divide-and-conquer recurrences T(n) = a · T(n/b) + f(n) → Master Theorem or recursion tree.
• Subtractive recurrences T(n) = T(n − k) + f(n) → telescoping sum.
• Unbalanced recurrences T(n) = T(α n) + T(β n) + f(n) → Akra–Bazzi method.
• Linear recurrences with constant coefficients (Fibonacci-style) → characteristic equation.

The art is recognising the shape and reaching for the right tool. Most algorithm-analysis recurrences fall into one of the categories above.

2. Setting Up the Recurrence — From Code to Equation

The mechanical recipe:

1. Identify what n is — the input size (length of array, number of nodes, magnitude of an integer, etc.).
2. Find the recursive call(s) and what input size each receives. If the function calls itself on inputs of sizes n₁, n₂, ..., n_k, those become the recursive terms.
3. Find the per-call non-recursive work — call this f(n). Includes loops, memory allocation, comparisons that aren’t part of a sub-call.
4. State a base case: T(c) = Θ(1) for some small c (often 0 or 1).

2.1 Worked Example — Merge Sort

def merge_sort(a, lo, hi):       # n = hi - lo
    if hi - lo <= 1: return       # base: T(1) = Θ(1)
    mid = (lo + hi) // 2
    merge_sort(a, lo, mid)        # T(n/2)
    merge_sort(a, mid, hi)        # T(n/2)
    merge(a, lo, mid, hi)         # Θ(n)

Two recursive calls each on n/2, plus a Θ(n) merge. The recurrence:

T(n) = 2 · T(n/2) + Θ(n)
T(1) = Θ(1)

This is the canonical Case 2 recurrence; Master Theorem gives T(n) = Θ(n log n).

2.2 Worked Example — Naive Recursive Sum

def rec_sum(arr, i):
    if i == len(arr): return 0    # T(0) = Θ(1)
    return arr[i] + rec_sum(arr, i + 1)   # T(n-1) + Θ(1)

One recursive call on size n − 1, constant post-work. Recurrence:

T(n) = T(n − 1) + Θ(1)
T(0) = Θ(1)

This is not divide-and-conquer; it’s subtractive. Solve by direct summation: T(n) = T(0) + n · Θ(1) = Θ(n).

2.3 Worked Example — Naive Recursive Fibonacci

def fib(n):
    if n < 2: return n            # T(0), T(1) = Θ(1)
    return fib(n-1) + fib(n-2)    # T(n-1) + T(n-2) + Θ(1)

Recurrence:

T(n) = T(n-1) + T(n-2) + Θ(1)
T(0) = T(1) = Θ(1)

This is a linear recurrence; the characteristic equation is x² = x + 1, with roots φ = (1+√5)/2 ≈ 1.618 and ψ = (1−√5)/2 ≈ −0.618. The dominant term gives T(n) = Θ(φⁿ) — exponential. (Fibonacci DP reduces this to O(n) via memoization.)

2.4 Common Recurrence Shapes

Shape	Source	Solution
T(n) = T(n/2) + Θ(1)	Binary Search	Θ(log n)
T(n) = 2T(n/2) + Θ(1)	Tree traversal	Θ(n)
T(n) = 2T(n/2) + Θ(n)	Merge Sort	Θ(n log n)
T(n) = 2T(n/2) + Θ(n²)	Heavy combine	Θ(n²)
T(n) = T(n/2) + Θ(n)	Linear-scan D&C	Θ(n)
T(n) = T(n − 1) + Θ(1)	Linear recursion	Θ(n)
T(n) = T(n − 1) + Θ(n)	Insertion sort recursive	Θ(n²)
T(n) = 2T(n − 1) + Θ(1)	Tower of Hanoi	Θ(2ⁿ)
T(n) = T(n − 1) + T(n − 2) + Θ(1)	Naive Fibonacci	Θ(φⁿ)
T(n) = T(√n) + Θ(1)	Repeated square-rooting	Θ(log log n)
T(n) = T(αn) + T(βn) + Θ(n), α + β = 1	Unequal D&C	Akra–Bazzi → Θ(n log n) typically

Memorize the shapes and their solutions. Most interview recurrences are minor variations of the above.

3. Tiny Worked Example — Tracing a Recurrence Tree

Take T(n) = 2 · T(n/2) + n, with T(1) = 1, and trace it by hand for n = 8.

                    T(8)              [does 8 work, then recurses]
                   /    \
               T(4)      T(4)         [each does 4 work]
              /  \      /  \
           T(2) T(2) T(2) T(2)        [each does 2 work]
           / \   / \  / \   / \
         T(1)..T(1)                   [each does 1 work, base]

Per-level work: depth 0 = 8, depth 1 = 4 + 4 = 8, depth 2 = 2 + 2 + 2 + 2 = 8, depth 3 = 1 × 8 = 8. Each of the log₂ 8 + 1 = 4 levels does 8 work; total = 4 · 8 = 32. In general for T(n) = 2T(n/2) + n, total = n · (log₂ n + 1) = Θ(n log n). ✓

This visual trace is the core idea behind the recursion-tree method (§5).

4. Method 1 — Substitution (Guess and Verify by Induction)

You guess a closed form for T(n) and prove it by strong induction on n. Surprisingly powerful when you have a good guess (often from staring at the recurrence’s similarity to a known one).

4.1 Recipe

1. Guess T(n) = O(g(n)) (or Θ(g(n))) for some explicit g.
2. Prove the guess by strong induction: assume T(k) ≤ c · g(k) for all k < n, then prove T(n) ≤ c · g(n) for sufficiently large n and some constant c.
3. Verify the base case: T(c₀) ≤ c · g(c₀) for some small c₀.

4.2 Worked Example — Substitution on Merge Sort’s Recurrence

Recurrence T(n) = 2T(n/2) + n, base T(1) = 1.

Guess T(n) ≤ c · n log₂ n for some constant c > 0.

Inductive step. Assume T(n/2) ≤ c · (n/2) · log₂(n/2). Then:

T(n)  =  2 · T(n/2) + n
      ≤  2 · [c · (n/2) · log₂(n/2)] + n
      =  c · n · log₂(n/2) + n
      =  c · n · (log₂ n − 1) + n
      =  c · n · log₂ n − c · n + n
      =  c · n · log₂ n + n · (1 − c)

For c ≥ 1, the term n · (1 − c) ≤ 0, so T(n) ≤ c · n · log₂ n. ✓

Base case. Pick n = 2: T(2) = 2 · T(1) + 2 = 2 + 2 = 4. Need 4 ≤ c · 2 · log₂ 2 = 2c, so c ≥ 2. ✓ Pick c = 2.

Conclusion. T(n) ≤ 2 · n · log₂ n for all n ≥ 2, so T(n) = O(n log n).

4.3 Common Substitution Mistake — Sloppy Constants

The classic student error: prove only T(n) ≤ c · g(n) + (something low-order). That is not the same as T(n) ≤ c · g(n) — the residual lower-order term invalidates the inductive hypothesis. You must absorb everything into c · g(n) exactly. See CLRS Ch. 4.3 for a worked example of this trap.

4.4 When Substitution Is Hard — You Need a Better Guess

If the substitution doesn’t go through, try a stronger guess. For example, T(n) = T(n/2) + 1 — the substitution T(n) ≤ c · log n succeeds, but T(n) ≤ c · log n − d for some constant d > 0 is easier (the extra slack absorbs the +1). This is the “strengthening the inductive hypothesis” trick from mathematical induction generally.

5. Method 2 — Recursion Tree (Sum Work by Level)

The recursion tree is a visualisation of the recursion. Each node is a sub-call and is labelled with the non-recursive work it does. Sum across all nodes to get the total cost.

5.1 Recipe

1. Draw the recursion tree (root = T(n), children = sub-calls).
2. Label each node with the non-recursive work f(...) it does.
3. Sum the work at each level (a level is all nodes with the same recursion depth).
4. Sum over all levels.

5.2 Worked Example — T(n) = T(n/3) + T(2n/3) + n (Unequal Split)

This is the recurrence for the worst-case Quickselect with median-of-medians pivot, or for Ternary Search tree analyses.

The tree is not balanced — one branch shrinks by a factor of 3, the other by 2/3. The shorter branch hits the base case at depth log₃ n; the longer branch at depth log_{3/2} n.

Per-level work. At every level, the total input size across all sub-calls equals (or is close to) n — because n/3 + 2n/3 = n, the work f(n) = n distributes across the level summing to n. So each level does Θ(n) work, until levels close to the bottom of the longer branch where some sub-trees have already terminated.

Number of levels. The longest path from root to leaf shrinks by 2/3 per step, so depth ≈ log_{3/2} n ≈ 1.71 · log₂ n.

Total work. Θ(n) per level × Θ(log n) levels = Θ(n log n).

(Akra–Bazzi confirms this analytically — see §7.)

5.3 Worked Example — T(n) = 4T(n/2) + n² (Many Subproblems, Heavy Combine)

a = 4, b = 2, f(n) = n². c* = log₂ 4 = 2, watershed n². Combine work matches watershed, so Master Theorem Case 2 (k=0) → T(n) = Θ(n² log n).

Recursion tree confirmation: at depth d, there are 4^d sub-calls each on n/2^d, so work per level is 4^d · (n/2^d)² = 4^d · n²/4^d = n². Constant per level × log₂ n levels = Θ(n² log n). ✓

6. Method 3 — Master Theorem

The Master Theorem gives a closed-form solution for the divide-and-conquer recurrence shape:

T(n) = a · T(n/b) + f(n)        (a ≥ 1, b > 1)

by comparing f(n) to the watershed function n^(log_b a). Three cases:

• Case 1 (f(n) = O(n^(log_b a − ε)) for some ε > 0): T(n) = Θ(n^(log_b a)). Leaves dominate.
• Case 2 (f(n) = Θ(n^(log_b a) · log^k n) for k ≥ 0): T(n) = Θ(n^(log_b a) · log^(k+1) n). Every level equal.
• Case 3 (f(n) = Ω(n^(log_b a + ε)) and regularity): T(n) = Θ(f(n)). Root dominates.

The Master Theorem is the right tool when the recurrence is actually divide-and-conquer. It does not apply to subtractive recurrences T(n) = T(n−1) + ... or to unbalanced splits like T(n) = T(n/3) + T(2n/3) + .... For those, use recursion tree or Akra–Bazzi.

See Master Theorem for full statement with worked examples and the regularity condition.

7. Method 4 — Akra–Bazzi (For Unbalanced Splits)

The Akra–Bazzi method (Akra & Bazzi 1998) generalises the Master Theorem to recurrences of the form:

T(n) = Σ_{i=1..k}  a_i · T(b_i n + h_i(n))  +  g(n)

where each a_i ≥ 0, 0 < b_i < 1, the h_i(n) are small perturbations bounded by n / log² n, and g(n) is a “nice” positive function.

The solution: find p such that Σ a_i · b_i^p = 1 (the characteristic equation), then:

T(n) = Θ( n^p · ( 1 + ∫_1^n  g(u) / u^(p+1)  du ) )

7.1 Worked Example — T(n) = T(n/3) + T(2n/3) + n

Find p: (1/3)^p + (2/3)^p = 1. By inspection p = 1 works (1/3 + 2/3 = 1). Then:

T(n) = Θ( n · (1 + ∫_1^n  u/u²  du) )
     = Θ( n · (1 + ln n) )
     = Θ(n log n)

Same answer as the recursion-tree analysis in §5.2, but mechanical.

7.2 Why Akra–Bazzi Matters

Whenever your recurrence has unequal subproblem sizes (most commonly: a “good” pivot vs. “bad” partition split, or a divide-and-conquer that splits into chunks of different fractions of n), Akra–Bazzi is the right tool. The Master Theorem requires exactly one b; Akra–Bazzi handles arbitrary linear combinations.

For the Master Theorem’s gap cases (where f(n) differs from n^(log_b a) by only a logarithmic factor), Akra–Bazzi also gives a clean answer where the Master Theorem stays silent.

7.3 The Side Conditions, Precisely

The method is not unconditional; it carries three technical requirements that are worth stating exactly, because most algorithm-analysis recurrences satisfy them so trivially that it is easy to forget they exist. Writing the recurrence as T(x) = g(x) + Σ_{i=1..k} a_i · T(b_i·x + h_i(x)) for x ≥ x₀ (Akra–Bazzi method, conditions; the same conditions appear in Leighton’s 1996 manuscript):

1. Coefficients. Each a_i > 0 and each 0 < b_i < 1 are constants. (Strictly positive weights, strictly shrinking subproblems.)
2. Perturbations are small. Each h_i(x) must satisfy |h_i(x)| ∈ O(x / (log x)²). This is precisely the slack that lets you ignore the floors and ceilings in real code — replacing T(⌈n/3⌉) with T(n/3) introduces a perturbation of O(1), which is comfortably inside O(x / log² x), so it changes nothing.
3. g grows polynomially. The non-recursive term must satisfy a polynomial-growth condition: in Leighton’s formulation, |g'(x)| ∈ O(x^c) for some constant c (equivalently, g lies in a class where g(λx) and g(x) differ by only a bounded factor for bounded λ). Every g(x) = x^a · log^b x qualifies; what does not qualify is a function that oscillates or jumps wildly — e.g., a g with 2^{sin x}-style behavior. For such pathological combine functions the integral in the result formula may not capture the true growth, and you should fall back to a recursion-tree or direct-summation argument.

The takeaway: for the recurrences that arise from actual divide-and-conquer code — polynomially-bounded combine work, fractional shrinkage, floor/ceiling rounding — all three conditions hold automatically, and Akra–Bazzi applies mechanically. The conditions only bite on artificially constructed g.

8. Special Recurrences and Their Solutions

8.1 T(n) = T(√n) + 1

Repeated square-rooting. The sub-call shrinks n → √n → n^(1/4) → n^(1/8) → .... After k steps, the size is n^(1/2^k). Termination when n^(1/2^k) ≤ 2, i.e., 2^k ≥ log₂ n, i.e., k ≥ log₂ log₂ n. Each step does Θ(1) work, so T(n) = Θ(log log n).

This recurrence shows up in van Emde Boas trees and other “successor in a sparse universe” structures.

8.2 T(n) = T(αn) + T(βn) + n, α + β = 1

Akra–Bazzi: α^p + β^p = 1 is satisfied at p = 1 (since α + β = 1), so T(n) = Θ(n log n). Quickselect/partition-style algorithms with constant-fraction split satisfy this (e.g., α = 1/3, β = 2/3 from §5.2).

8.3 T(n) = T(αn) + T(βn) + n, α + β < 1

Now the total subproblem size shrinks geometrically per level. The non-recursive work n dominates the root, and the recursion bottoms out fast. Akra–Bazzi: p satisfies α^p + β^p = 1 which now requires p < 1, so n^p < n. The integral converges:

T(n) = Θ(n · (1 + integral)) = Θ(n)

Linear time. This is the recurrence for Median of Medians selection: T(n) = T(n/5) + T(7n/10) + Θ(n). Here 1/5 + 7/10 = 9/10 < 1, so T(n) = Θ(n). The factor 5 is exactly tuned so that the sum is less than 1 — that’s why median-of-medians works.

8.4 T(n) = aT(n − 1) + Θ(1)

Subtractive with multiplicative branching. a = 1 gives Θ(n); a = 2 gives Θ(2^n) (Tower of Hanoi); a > 1 in general gives Θ(aⁿ). Solve by direct summation: T(n) = Σ_{k=0..n} a^k = (a^(n+1) − 1) / (a − 1) = Θ(aⁿ) for a > 1.

8.5 Linear Recurrences with Constant Coefficients

Recurrences like T(n) = c₁ T(n−1) + c₂ T(n−2) + ... + c_k T(n−k) are solved via the characteristic polynomial x^k = c₁ x^(k−1) + c₂ x^(k−2) + ... + c_k. The roots r_i give the closed-form T(n) = Σ A_i · r_iⁿ. The dominant root determines Θ(...).

Fibonacci: T(n) = T(n−1) + T(n−2), characteristic x² = x + 1, roots φ ≈ 1.618 and ψ ≈ −0.618, dominant φ, so T(n) = Θ(φⁿ).

Knuth TAOCP Vol. 1 §1.2.8 gives a full treatment of linear recurrences via generating functions.

9. A Pseudocode Recipe — How to Approach Any New Recurrence

solve(T):
    classify the recurrence shape:
        if T(n) = a·T(n/b) + f(n)        → try Master Theorem
        if T(n) = Σ a_i·T(b_i·n) + g(n)  → try Akra–Bazzi
        if T(n) = T(n−k) + f(n)          → telescope/sum directly
        if T(n) = c₁·T(n−1) + c₂·T(n−2)  → characteristic equation
        otherwise                         → recursion tree, then verify by substitution
    if Master Theorem doesn't fit cleanly:
        check for a gap case, use Akra–Bazzi or recursion tree
    sanity-check by trying small n by hand

10. Pitfalls

10.1 Wrong Recurrence from Code

The most common error: setting up the wrong recurrence. Common sub-errors:

• Missing recursive calls. If your function calls solve(left) and solve(right), that’s 2T(...), not T(...).
• Wrong subproblem size. solve(left) where left has size n − 1 (not n/2!) gives a subtractive recurrence, not a divide-and-conquer.
• Counting only one branch. If both branches happen unconditionally, you have 2T(...). If only one branch executes (e.g., binary search’s if-else picks one half), you have T(...).

Always trace through with a concrete example to confirm the recurrence shape.

10.2 Forgetting Non-Recursive Work

Inside the recursive function, every line that isn’t a recursive call counts toward f(n). A loop that scans the input is Θ(n), not Θ(1). List concatenation a + b in Python is Θ(n), not Θ(1). Hash-map operations are Θ(1) average but worst-case Θ(n).

10.3 Misusing Master Theorem on Non-D&C Recurrences

The Master Theorem requires T(n) = a · T(n/b) + f(n) exactly. T(n) = T(n−1) + n is not of this form (it’s subtractive). Solve subtractive recurrences by direct summation.

10.4 Sloppy Substitution

Don’t prove T(n) ≤ c · n log n + n and conclude T(n) = O(n log n) — the residual + n invalidates the induction. Either pick a stronger inductive hypothesis (T(n) ≤ c · n log n − d) or absorb the residual.

10.5 Forgetting Base Cases

A recurrence is incomplete without base cases. T(n) = 2T(n/2) + n with no base case is undefined. Always specify T(1) = ? (or some other small n).

10.6 Confusing log_b a with log a / b

The watershed exponent in the Master Theorem is log_b a, the logarithm of a, base b. Not log(a) / b. Not log_b n. Get it wrong and your answer will be nonsense.

10.7 Overlooking the Akra–Bazzi Side Conditions

Akra–Bazzi requires g(n) to be polynomially bounded, the b_i to be in (0, 1), and the perturbations h_i(n) to be small. Pathological combine functions or shrinkage factors equal to 1 (no shrinkage) break the method.

11. Diagram — Recursion Tree for T(n) = 2T(n/2) + n

flowchart TD
    R["T(n): work n"]
    L1a["T(n/2): work n/2"]
    L1b["T(n/2): work n/2"]
    L2a["T(n/4)"]
    L2b["T(n/4)"]
    L2c["T(n/4)"]
    L2d["T(n/4)"]
    L3["..."]
    Leaf["T(1) leaves: n leaves total"]

    R --> L1a
    R --> L1b
    L1a --> L2a
    L1a --> L2b
    L1b --> L2c
    L1b --> L2d
    L2a --> L3
    L2b --> L3
    L2c --> L3
    L2d --> L3
    L3 --> Leaf

    Sum["Per-level work: n at every level<br/>Number of levels: log₂ n + 1<br/>Total: n · (log₂ n + 1) = Θ(n log n)"]

What this diagram shows. The recursion tree for the merge-sort recurrence T(n) = 2T(n/2) + n. The root does n work. At depth 1 there are 2 nodes each doing n/2 work — total n. At depth 2 there are 4 nodes each doing n/4 work — still total n. This constant-work-per-level property is the distinguishing feature of Master Theorem Case 2: the work distributes evenly across all log n levels, contributing Θ(n log n) total. If the per-level total had grown with depth, leaves would dominate (Case 1). If it had shrunk, the root would dominate (Case 3).

12. Common Interview Problems

Algorithm	Recurrence	Solution
Merge Sort	T(n) = 2T(n/2) + n	Θ(n log n) (MT Case 2)
Binary Search	T(n) = T(n/2) + 1	Θ(log n) (MT Case 2, k=0)
Quicksort worst	T(n) = T(n−1) + n	Θ(n²) (subtractive, telescope)
Quicksort avg	T(n) = 2T(n/2) + n	Θ(n log n)
Karatsuba multiplication	T(n) = 3T(n/2) + n	Θ(n^log₂3) (MT Case 1)
Strassen matrix multiply	T(n) = 7T(n/2) + n²	Θ(n^log₂7) (MT Case 1)
Median of Medians	T(n) = T(n/5) + T(7n/10) + n	Θ(n) (Akra–Bazzi)
Naive recursive Fibonacci	T(n) = T(n−1) + T(n−2) + 1	Θ(φⁿ) (characteristic)
Tower of Hanoi	T(n) = 2T(n−1) + 1	Θ(2ⁿ) (subtractive multiplicative)

13. Open Questions

• How do you handle a recurrence like T(n) = T(n − √n) + 1? Not Master Theorem (not T(n/b) shape), not Akra–Bazzi (subtractive, not multiplicative). The right tool is iteration: each step removes about √n from the argument, so substitute n = m² — then one step takes m² → m² − m ≈ (m − ½)², i.e. m drops by about ½ per step, giving Θ(m) = Θ(√n) steps, each doing Θ(1) work. Hence T(n) = Θ(√n). (This is the flavor of subtractive recurrence in CLRS Ch. 4’s problem set; I have not pinned the exact problem number, so I cite the chapter rather than a specific numbered problem — the earlier “Problem 4-6” attribution was unverified.)
• Are there recurrences with no closed-form solution? Yes — non-linear recurrences like T(n) = T(n−1)² + 1 can have super-exponential growth that only admits asymptotic-class statements.
• When does the recurrence-tree method fail? Mainly when the tree is very irregular (different sub-problems at different depths) — but Akra–Bazzi or careful summation usually rescues it.

14. See Also

• Master Theorem — closed-form for T(n) = a · T(n/b) + f(n)
• Big-O Notation, Big-Omega and Big-Theta — what we are solving for
• Merge Sort — canonical Case 2 recurrence
• Binary Search — T(n) = T(n/2) + 1
• Quicksort — both Case 2 average and subtractive worst case
• Median of Medians — Akra–Bazzi territory
• Fibonacci DP — naive recursive Θ(φⁿ) collapsed to Θ(n) via memoization
• Recursion vs Iteration — the recursion side of every recurrence
• Divide and Conquer Paradigm — the meta-pattern that produces master-theorem recurrences
• SWE Interview Preparation MOC