Recurrence relations

T(n) = T(n - 1) + O(1) describes a recursion that does constant work and calls itself on a problem one smaller, such as factorial or linear recursion over an array. Unrolling gives n levels of constant work, so T(n) = Θ(n). The depth is also n, so the stack needs O(n) space.

Step through the factorial call stack and count n calls.

1static long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }   // T(n) = T(n-1) + O(1) = Theta(n)

1static long factorial(int n) {
2    if (n == 0) return 1;              // base case
3    return n * factorial(n - 1);       // recursive case
4}

T(n) = 2T(n/2) + O(n) splits into two halves and does linear work to combine, as in merge sort. There are log₂ n levels and each level costs about n, so T(n) = Θ(n log n).

Open the recursion-tree view: choose this recurrence and read the work per level.

1static void mergeSort(int[] a, int lo, int hi) {   // T(n) = 2T(n/2) + O(n)
2    if (hi - lo < 2) return;
3    int mid = (lo + hi) >>> 1;
4    mergeSort(a, lo, mid); mergeSort(a, mid, hi);
5    merge(a, lo, mid, hi);                          // O(n) work
6}

1// T(n) = a * T(n / b) + f(n): each call does f(n) work itself and spawns a smaller calls
2static int solve(int n) {
3    if (n <= 1) return 1;                // base case: constant work
4    int work = f(n);                     // work done in THIS call
5    for (int k = 0; k < a; k++) solve(n / b);
6    return work;
7}
8// total work = sum of f(size) over every node of the recursion tree

The substitution method guesses the solution and proves it by induction. To show T(n) = 2T(n/2) + n is O(n log n), assume T(m) ≤ c·m·log₂ m for m < n. Then T(n) ≤ 2·c·(n/2)·log₂(n/2) + n = c·n·log₂ n - c·n + n ≤ c·n·log₂ n whenever c ≥ 1.

Guess from a recursion tree, then prove. A wrong guess fails in the induction step, which tells you to adjust it.

A recursion tree draws each call as a node labelled with its own non-recursive cost. Sum the cost per level and then over the levels. For T(n) = 2T(n/2) + n each level costs n and there are log₂ n + 1 levels. For T(n) = T(n - 1) + 1 the tree is a chain of n nodes.

Choose a recurrence below, set n, and read the total and per-level work.

1// T(n) = a * T(n / b) + f(n): each call does f(n) work itself and spawns a smaller calls
2static int solve(int n) {
3    if (n <= 1) return 1;                // base case: constant work
4    int work = f(n);                     // work done in THIS call
5    for (int k = 0; k < a; k++) solve(n / b);
6    return work;
7}
8// total work = sum of f(size) over every node of the recursion tree

For T(n) = aT(n/b) + f(n) with a ≥ 1, b > 1, compare f(n) with n^(log_b a). Case 1: f is polynomially smaller, T = Θ(n^(log_b a)) (leaves dominate). Case 2: f = Θ(n^(log_b a)), T = Θ(n^(log_b a) log n) (every level equal). Case 3: f is polynomially larger and satisfies the regularity condition a·f(n/b) ≤ c·f(n) with c < 1, T = Θ(f(n)) (root dominates).

Enter a, b and f in the tool to see the case and the result.

The Akra-Bazzi method handles recurrences the Master theorem cannot, such as unequal splits: T(n) = Σ aᵢ T(bᵢ n) + g(n). Find p with Σ aᵢ bᵢᵖ = 1; then T(n) = Θ(nᵖ (1 + ∫₁ⁿ g(u) / uᵖ⁺¹ du)).

Example: T(n) = T(n/3) + T(2n/3) + n has (1/3)ᵖ + (2/3)ᵖ = 1 at p = 1, and the integral gives log n, so T(n) = Θ(n log n). This is the cost of a quick sort whose pivots always split 1:2.