Analyzing Recursion: Recurrences & the Master Theorem

Writing a recurrence T(n)

You already know how to count the cost of a loop. But what is the cost of a function that calls *itself*? You cannot just stare at it, because its work depends on the work of a smaller copy of the same problem. The trick is to give that cost a name — call it T(n), the time to solve a problem of size n — and then write an equation that says: "the time for size n equals the time for the smaller pieces, plus whatever I do to split them and combine them." That self-referential equation is a [[recurrence-relation|recurrence relation]].

Reading code into a recurrence is mechanical once you see the pattern. For each recursive call, add one T(smaller size). Then add a separate term for the non-recursive work in that call — the loops, comparisons, and merges that happen before or after the recursion. Finally, write a base case: the size at which the function stops recursing, which costs a constant, T(1) = O(1). Here is [[merge-sort|merge sort]], read line by line into its recurrence.

void mergeSort(vector<int>& a, int lo, int hi) {
    if (hi - lo <= 1) return;          // base case: T(1) = O(1)
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);             // one call on n/2  -> T(n/2)
    mergeSort(a, mid, hi);             // one call on n/2  -> T(n/2)
    merge(a, lo, mid, hi);             // scan and merge   -> O(n)
}
// Reading the lines:  T(n) = 2*T(n/2) + O(n),  T(1) = O(1)

Solving by unrolling

Before reaching for a theorem, it helps to solve a recurrence the honest way: unroll it. You substitute the recurrence into itself, level after level, until you spot the pattern, then add up the work across all the levels. Take the simplest recursive cost, T(n) = T(n/2) + O(1) — one call on half, plus constant work. This is exactly [[binary-search|binary search]]: throw away half, do one comparison.

T(n) = T(n/2)   + 1
     = T(n/4)   + 1 + 1
     = T(n/8)   + 1 + 1 + 1
     ...
     = T(n/2^k) + k         // after k steps
Stop when n/2^k = 1  =>  2^k = n  =>  k = log2(n)
So T(n) = T(1) + log2(n) = O(log n).

The same picture explains merge sort, but the accounting changes. Draw the recursion tree: the root is a problem of size n, its two children are size n/2, their children size n/4, and so on. The tree is log n levels deep — but at *every* level the merges across all the nodes add up to O(n). So you have log n levels, each costing O(n), and the total is the product: O(n log n).

level 0:        [ n ]                       work this level: n
level 1:     [n/2] [n/2]                     work this level: n/2 + n/2 = n
level 2:  [n/4][n/4][n/4][n/4]               work this level: 4*(n/4) = n
  ...        ...   ...   ...   ...           ...
level log n: [1][1][1] ... [1]               work this level: n*(1)    = n
             ----------------------------------------------------
             log n levels  x  n per level  =  O(n log n)

The Master Theorem as a cookbook

Unrolling works, but it is tedious. The [[master-theorem|Master Theorem]] is a shortcut for [[divide-and-conquer|divide-and-conquer]] recurrences of one specific shape: T(n) = a·T(n/b) + f(n), where you make a recursive calls, each on a problem b times smaller, and spend f(n) on the split-and-combine work outside the recursion. For merge sort a = 2, b = 2, f(n) = n. The theorem compares the growth of the recursion (captured by n raised to the power log base b of a) against the growth of f(n), and picks the winner.

Master Theorem  (for  T(n) = a*T(n/b) + f(n),  a >= 1, b > 1)
Let  c = log_b(a).   Compare f(n) against n^c:

  Case 1  f(n) grows slower than n^c   ->  T(n) = O(n^c)
          (the leaves dominate)
  Case 2  f(n) grows like  n^c         ->  T(n) = O(n^c * log n)
          (every level costs about the same)
  Case 3  f(n) grows faster than n^c   ->  T(n) = O(f(n))
          (the root's own work dominates)

1. Merge sort: T(n) = 2·T(n/2) + n. Here a = 2, b = 2, so c = log_2(2) = 1, and n^c = n. The extra work f(n) = n grows like n^c = n — a tie. That is Case 2, giving T(n) = O(n^1 · log n) = O(n log n). Matches the recursion tree exactly.
2. Binary search: T(n) = 1·T(n/2) + O(1). Here a = 1, b = 2, so c = log_2(1) = 0, and n^c = n^0 = 1. The extra work f(n) = O(1) grows like n^c = 1 — another tie. Case 2 again, giving T(n) = O(1 · log n) = O(log n). Same answer the unrolling gave us.
3. A Case-1 taste: T(n) = 8·T(n/2) + n. Now c = log_2(8) = 3, so n^c = n^3, which grows much faster than f(n) = n. The leaves dominate: T(n) = O(n^3). The recursion's branching, not the per-call work, sets the cost.