Recurrence Relations: Recursion, Described in Math

A recurrence relation defines a function in terms of its own value at smaller inputs. For algorithm analysis, recurrences model the runtime of recursive algorithms: T(n) is the cost of a problem of size n, expressed as the cost of its subproblems plus the work to split and recombine.

T(n) = a · T(n/b) + f(n)

• a = number of subproblems
• n/b = size of each subproblem
• f(n) = cost of dividing and combining
• base case — T(1) = O(1), the point where recursion stops

Three canonical recurrences: binary search T(n) = T(n/2) + O(1), merge sort T(n) = 2T(n/2) + O(n), naive Fibonacci T(n) = T(n-1) + T(n-2) + O(1). The recurrence is a complete — if compact — description of the algorithm’s cost structure; solving it yields the asymptotic class.

The Substitution Method: Guess and Verify

1. Guess the asymptotic form — from intuition, a recursion tree, or a known pattern.
2. Verify by induction: assume the bound holds for all smaller inputs, substitute it into the recurrence, and confirm it holds for n.

For T(n) = 2T(n/2) + n, guess T(n) = O(n log n). Induction hypothesis: T(n/2) = c(n/2) log(n/2). Then:

T(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    for c ≥ 1

The guess is proven. Substitution is the most general method — it works when the Master Theorem’s conditions don’t apply — but it needs a good guess, a valid induction hypothesis, and careful base cases.

The Recursion-Tree Method: Seeing the Cost

Draw the recurrence as a tree: the root costs f(n), each node branches into a children of size n/b. Sum the work at each level, then sum across levels down to the base case. For T(n) = 2T(n/2) + n:

          n                    ← level 0: one node, cost n
        /     \
      n/2     n/2              ← level 1: two nodes, total n
     /  \     /  \
   n/4  n/4  n/4  n/4          ← level 2: four nodes, total n
    ...          ...

Every level totals n, and there are log₂ n levels, so T(n) = Θ(n log n). Recursion trees shine when the work per level is irregular — they show exactly where the cost concentrates, which substitution hides.

The Master Theorem

For T(n) = aT(n/b) + f(n) with a ≥ 1, b > 1, the theorem compares f(n) with the critical exponent c* = log_b(a) — the cost implied by the branching structure alone:

1. Case 1 (subproblem-dominated): if f(n) = O(n^(c* − ε)), the recursion itself dominates → T(n) = Θ(n^c*).
2. Case 2 (balanced): if f(n) = Θ(n^c* · log^k n), work is spread evenly across levels → T(n) = Θ(n^c* · log^(k+1) n).
3. Case 3 (combine-dominated): if f(n) = Ω(n^(c* + ε)) and a·f(n/b) ≤ c·f(n) for some c < 1, the combine step dominates → T(n) = Θ(f(n)).

Worked applications:

Case 2 also covers f(n) = n^c* · log^k n; case 3 needs the regularity condition a·f(n/b) ≤ c·f(n) — verify it whenever f(n) is not a clean polynomial.

Common Recurrences, Mapped

Quicksort deserves special attention: with a bad pivot the recurrence degrades to T(n) = T(n-1) + O(n) — one subproblem of size n−1 plus O(n) partitioning — solving to O(n²). With random pivots the average behaves like merge sort’s recurrence and lands at O(n log n). Same algorithm, two recurrences, two classes.

Worked Example: Merge Sort, Step by Step

Solve T(n) = 2T(n/2) + n — the n is the cost of merging two sorted halves.

1. Split: dividing in half is O(1) (an index computation); folded into the merge cost.
2. Level cost: at depth k there are 2^k subproblems of size n/2^k; each merge costs n/2^k, so a level costs 2^k · n/2^k = n.
3. Depth: log₂ n levels until subproblems hit size 1.
4. Total: log₂ n levels × n per level = Θ(n log n).

The Master Theorem gives the same answer in one line (case 2). Use the recursion tree when you want to see where the cost goes; use the theorem when you want speed — they must agree.

Practice Trajectory

1. Write recurrences for binary search, merge sort, and quicksort’s worst case; solve each with the Master Theorem where possible.
2. Draw the recursion tree for T(n) = 3T(n/4) + n² and sum the level costs to the base case.
3. Prove T(n) = T(n/2) + O(1) → O(log n) by substitution (induction).
4. Find a recurrence the Master Theorem cannot solve (e.g. T(n) = T(n-1) + log n) and solve it by unrolling.
5. Derive merge sort’s O(n log n) three ways — recursion tree, substitution, Master Theorem — and confirm all three agree.

When It’s the Right Tool