Chapter 59 of 65

Recurrence Relations & Master Theorem

On this page

For a loop, finding the time complexity is easy: count how many times the loop runs. But how do you find the time complexity of a function that calls itself?

static void solve(int n) {
    if (n <= 1) return;
    solve(n / 2);
    solve(n / 2);
    for (int i = 0; i < n; i++) { /* O(1) work */ }
}

You can't just count loops here, because part of the work is hidden inside the recursive calls. Instead, we write an equation that describes the running time in terms of itself, and then solve that equation.

A recurrence relation is an equation that defines T(n), the running time on an input of size n, using the running time on smaller inputs, together with a base case.

In the Divide and Conquer chapter, you met the recursion tree and a simple form of the Master Theorem. In this chapter, we go deeper: how to write a recurrence from code, four methods to solve it, the full Master Theorem with all its conditions, recurrences it cannot solve, and many worked examples of the kind asked in placement tests, GATE and interviews.


Writing a Recurrence from Code

The recipe is always the same:

T(n) = (number of recursive calls) × T(size of each call)
     + (work done in this call, outside the recursive calls)

plus a base case, usually T(1) = O(1)

For the function at the top of this chapter:

2 recursive calls, each on n/2   → 2T(n/2)
one loop of n iterations          → + n

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

Let's practise on some common shapes:

Code shape

Recurrence

Solution

One call on n - 1, O(1) work (factorial, sum of array)

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

Θ(n)

One call on n - 1, a loop of n (recursive Selection Sort)

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

Θ(n²)

Two calls on n - 1, O(1) work (Tower of Hanoi)

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

Θ(2ⁿ)

One call on n / 2, O(1) work (Binary Search)

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

Θ(log n)

Two calls on n / 2, O(1) work (findMax)

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

Θ(n)

Two calls on n / 2, a loop of n (Merge Sort)

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

Θ(n log n)

One call on n / 2, a loop of n

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

Θ(n)

Calls on n - 1 and n - 2 (naive Fibonacci)

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

Θ(1.618ⁿ)

Two details trip students up:

  • Count calls, not lines. return f(n/2) + f(n/2); makes two calls, so it is 2T(n/2). Storing the result in a variable and reusing it makes it T(n/2). This is exactly the fast power trick from the Divide and Conquer chapter.

  • The extra work matters. T(n) = 2T(n/2) + 1 is Θ(n), while T(n) = 2T(n/2) + n is Θ(n log n). The only difference is the loop.

We'll usually assume n is a power of the dividing factor (like n = 2ᵏ), so that n/2, n/4, ... are whole numbers. Floors and ceilings like ⌊n/2⌋ almost never change the Big O answer.


Method 1: Back Substitution (Iteration)

The most direct method: keep replacing T(smaller) using the recurrence itself until you spot a pattern, then jump to the base case.

Example 1: T(n) = T(n-1) + n, with T(1) = 1

T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
     ...
     = T(1) + 2 + 3 + ... + n
     = 1 + 2 + 3 + ... + n
     = n(n+1)/2

T(n) = Θ(n²)

This is the recurrence of Quick Sort's worst case and of recursive Selection Sort.

Example 2: T(n) = 2T(n-1) + 1, with T(1) = 1 (Tower of Hanoi)

T(n) = 2T(n-1) + 1
     = 2[2T(n-2) + 1] + 1         = 4T(n-2) + 2 + 1
     = 4[2T(n-3) + 1] + 2 + 1     = 8T(n-3) + 4 + 2 + 1
     ...
     = 2ᵏ T(n-k) + (2ᵏ⁻¹ + ... + 2 + 1)

Stop when n - k = 1, so k = n - 1:

T(n) = 2ⁿ⁻¹ × 1 + (2ⁿ⁻¹ - 1)
     = 2ⁿ - 1

T(n) = Θ(2ⁿ)
T(n) = T(n/2) + 1
     = T(n/4) + 1 + 1
     = T(n/8) + 3
     ...
     = T(n/2ᵏ) + k

Stop when n/2ᵏ = 1, so k = log₂ n:

T(n) = T(1) + log₂ n = log₂ n + 1

T(n) = Θ(log n)

Example 4: T(n) = 2T(n/2) + n, with T(1) = 1 (Merge Sort)

T(n) = 2T(n/2) + n
     = 2[2T(n/4) + n/2] + n       = 4T(n/4) + 2n
     = 4[2T(n/8) + n/4] + 2n      = 8T(n/8) + 3n
     ...
     = 2ᵏ T(n/2ᵏ) + k·n

Stop when k = log₂ n (so 2ᵏ = n):

T(n) = n·T(1) + n log₂ n
     = n log₂ n + n

T(n) = Θ(n log n)

Checking the Formulas with Code

A quick way to gain confidence in a closed form is to compute the recurrence directly and compare. This program evaluates all four recurrences for powers of 2:

class Main {

    // T(n) = T(n - 1) + n,   T(1) = 1     (e.g. Selection Sort, Quick Sort worst case)
    static long linear(long n) {
        if (n == 1) return 1;
        return linear(n - 1) + n;
    }

    // T(n) = 2T(n - 1) + 1,  T(1) = 1     (Tower of Hanoi moves)
    static long hanoi(long n) {
        if (n == 1) return 1;
        return 2 * hanoi(n - 1) + 1;
    }

    // T(n) = T(n / 2) + 1,   T(1) = 1     (Binary Search)
    static long halving(long n) {
        if (n == 1) return 1;
        return halving(n / 2) + 1;
    }

    // T(n) = 2T(n / 2) + n,  T(1) = 1     (Merge Sort)
    static long mergeSort(long n) {
        if (n == 1) return 1;
        return 2 * mergeSort(n / 2) + n;
    }

    static long log2(long n) {
        return 63 - Long.numberOfLeadingZeros(n);   // exact for powers of 2
    }

    public static void main(String[] args) {

        System.out.println(" n | T(n-1)+n  formula | 2T(n-1)+1     formula | T(n/2)+1  formula | 2T(n/2)+n  formula");

        for (long n = 1; n <= 32; n *= 2) {
            System.out.printf("%2d | %8d  %7d | %10d  %10d | %8d  %7d | %9d  %7d%n",
                n,
                linear(n),    n * (n + 1) / 2,
                hanoi(n),     (1L << n) - 1,
                halving(n),   log2(n) + 1,
                mergeSort(n), n * log2(n) + n);
        }
    }
}

Output:

 n | T(n-1)+n  formula | 2T(n-1)+1     formula | T(n/2)+1  formula | 2T(n/2)+n  formula
 1 |        1        1 |          1           1 |        1        1 |         1        1
 2 |        3        3 |          3           3 |        2        2 |         4        4
 4 |       10       10 |         15          15 |        3        3 |        12       12
 8 |       36       36 |        255         255 |        4        4 |        32       32
16 |      136      136 |      65535       65535 |        5        5 |        80       80
32 |      528      528 | 4294967295  4294967295 |        6        6 |       192      192

Every column matches its formula. Notice how differently they grow: at n = 32, Binary Search needs 6 steps, Merge Sort 192, the quadratic recurrence 528, and the Hanoi recurrence more than 4 billion.


Method 2: The Substitution Method (Guess and Prove)

Sometimes back substitution gets messy. The substitution method works in two steps:

  1. Guess the form of the answer (from experience, or from a recursion tree).

  2. Prove it with mathematical induction.

Example: Prove that T(n) = 2T(n/2) + n is O(n log n)

Guess: T(n) ≤ c · n log₂ n for some constant c, for all powers of 2 with n ≥ 2.

Inductive step: assume the guess holds for n/2, that is, T(n/2) ≤ c · (n/2) log₂(n/2). Then:

T(n) = 2T(n/2) + n
     ≤ 2 · c · (n/2) · log₂(n/2) + n
     = c · n · (log₂ n - 1) + n
     = c · n log₂ n - c·n + n
     ≤ c · n log₂ n          as long as c ≥ 1

Base case: with T(1) = 1, we get T(2) = 2·1 + 2 = 4. We need 4 ≤ c · 2 · log₂ 2 = 2c, so c ≥ 2.

Choosing c = 2 satisfies both conditions, so T(n) ≤ 2n log₂ n for all powers of 2 from n = 2 onward. Therefore T(n) = O(n log n).

Why did we start at n = 2? Because at n = 1, c · 1 · log₂ 1 = 0, and T(1) = 1 is not ≤ 0. Big O only needs the bound to hold from some point onward, so this is allowed.

A Classic Wrong Proof

Watch this "proof" that the same recurrence is O(n):

Guess: T(n) ≤ c·n
T(n) = 2T(n/2) + n
     ≤ 2 · c · (n/2) + n
     = c·n + n
     = (c + 1)·n
     = O(n)        ← WRONG!

The mistake: induction must prove the exact same statement T(n) ≤ c·n, with the same constant c. We got (c + 1)·n, which is larger than c·n. The constant grows by one at every level, so the proof fails. Writing "= O(n)" in the middle of an induction hides this error. Always finish with the exact form you assumed.


Method 3: The Recursion Tree

Draw the calls as a tree, write the extra work at each node, add up each level, then add up the levels. This is the best method for building intuition, and the Master Theorem is really just a summary of it.

The Divide and Conquer chapter used it for 2T(n/2) + n, where every level did the same work n. Here are the other two possibilities.

Level Costs Decrease: T(n) = 3T(n/4) + n²

Level 0:                 n²                          → n²
Level 1:     (n/4)²    (n/4)²    (n/4)²              → 3n²/16
Level 2:     9 nodes, each (n/16)²                   → 9n²/256 = (3/16)² n²
  ...
Level i:     3ⁱ nodes, each (n/4ⁱ)²                  → (3/16)ⁱ n²

The level costs form a decreasing geometric series with ratio 3/16:

Total ≤ n² × (1 + 3/16 + (3/16)² + ...)
      = n² × 1 / (1 - 3/16)
      = (16/13) n²

T(n) = Θ(n²)    ← the root's work dominates

Level Costs Increase: T(n) = 4T(n/2) + n

Level 0:     1 node of size n          → n
Level 1:     4 nodes of size n/2       → 2n
Level 2:     16 nodes of size n/4      → 4n
  ...
Level i:     4ⁱ nodes of size n/2ⁱ     → 2ⁱ n
  ...
Leaves:      4^(log₂ n) = n² leaves    → n² × T(1)

Now the level costs double every level, so the last level is the biggest and it dominates the whole sum:

T(n) = Θ(n²)    ← the leaves dominate

Uneven Splits: T(n) = T(n/3) + T(2n/3) + n

The Master Theorem cannot handle two different sizes, but a recursion tree can:

Level 0:                 n                         → n
Level 1:          n/3          2n/3                → n
Level 2:      n/9   2n/9   2n/9   4n/9             → n
  ...

Every full level adds up to n. The shortest path from root to leaf follows the n/3 branch and has log₃ n levels. The longest path follows the 2n/3 branch and has log_{3/2} n levels (log base 3/2). Both are Θ(log n), so:

T(n) = Θ(n log n)

This is why Quick Sort stays O(n log n) even when the pivot always splits the array 1 : 2, or even 1 : 9.


Method 4: The Master Theorem

The Master Theorem is a ready-made answer for recurrences of this shape:

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

a ≥ 1     number of subproblems (a constant)
b > 1     each subproblem has size n/b (a constant)
f(n)      work done outside the recursive calls (positive for large n)

The key quantity is the critical exponent:

n^(log_b a)   = the total work done at the leaves

(the tree has a^(log_b n) = n^(log_b a) leaves)

The theorem compares f(n), the work at the root, with n^(log_b a), the work at the leaves. Whichever is polynomially larger wins. If they are equal, every level contributes and we get an extra log n.

Case

Condition

Result

What dominates

1

f(n) = O(n^(log_b a - ε)) for some ε > 0

Θ(n^(log_b a))

Leaves

2

f(n) = Θ(n^(log_b a) · logᵏ n) for some k ≥ 0

Θ(n^(log_b a) · logᵏ⁺¹ n)

All levels equally

3

f(n) = Ω(n^(log_b a + ε)) for some ε > 0, and a·f(n/b) ≤ c·f(n) for some c < 1 and all large n

Θ(f(n))

Root

A few notes on these conditions:

  • "Polynomially" smaller or larger means by a factor of n^ε. Being smaller or larger by only a log n factor is not enough for Case 1 or Case 3. When f(n) is larger by a log factor (like n log n against n), the extended Case 2 below handles it. When it is smaller by a log factor (like n / log n against n), see "When the Master Theorem Does NOT Apply".

  • Many textbooks state Case 2 only for k = 0, that is, f(n) = Θ(n^(log_b a)), which gives Θ(n^(log_b a) log n). The logᵏ form shown here is the more general version, and it covers recurrences like 2T(n/2) + n log n.

  • The extra condition in Case 3 is called the regularity condition. It says the work must really shrink as we go down the tree. For the usual f(n) = nᵈ or nᵈ logᵏ n, it is automatically true whenever d > log_b a, so in practice you only need to check it for unusual functions.

The Simple Form (Polynomial f)

When f(n) = Θ(nᵈ), the three cases become the simple comparison from the Divide and Conquer chapter:

T(n) = a·T(n/b) + Θ(nᵈ)

d < log_b a   → Θ(n^(log_b a))
d = log_b a   → Θ(nᵈ log n)
d > log_b a   → Θ(nᵈ)

A handy shortcut is to compare a with bᵈ directly, so you don't need logarithms:

a < bᵈ   → Case 3 (root wins)    → Θ(nᵈ)
a = bᵈ   → Case 2 (tie)          → Θ(nᵈ log n)
a > bᵈ   → Case 1 (leaves win)   → Θ(n^(log_b a))

For example, in T(n) = 4T(n/2) + n²: a = 4 and bᵈ = 2² = 4. They are equal, so the answer is Θ(n² log n).


Worked Examples

For each one: find a, b, f(n), compute n^(log_b a), compare.

Example 1: T(n) = 9T(n/3) + n

a = 9, b = 3, f(n) = n
n^(log₃ 9) = n²
f(n) = n = O(n^(2 - ε)) with ε = 1   → Case 1

T(n) = Θ(n²)

Example 2: T(n) = T(2n/3) + 1

a = 1, b = 3/2, f(n) = 1
n^(log_{3/2} 1) = n⁰ = 1
f(n) = Θ(1) = Θ(n⁰ · log⁰ n)          → Case 2 with k = 0

T(n) = Θ(log n)

Note that b does not have to be a whole number. It only has to be a constant greater than 1.

Example 3: T(n) = 3T(n/4) + n log n

a = 3, b = 4, f(n) = n log n
n^(log₄ 3) ≈ n^0.793
f(n) = n log n = Ω(n^(0.793 + ε)), e.g. ε = 0.2   → Case 3 candidate

Regularity: a·f(n/b) = 3 · (n/4) · log(n/4)
                     ≤ (3/4) · n log n
            so c = 3/4 < 1 works (holds)

T(n) = Θ(n log n)

Example 4: T(n) = 2T(n/2) + n log n

a = 2, b = 2, f(n) = n log n
n^(log₂ 2) = n
f(n) = n · log¹ n = Θ(n^(log_b a) · log¹ n)   → Case 2 with k = 1

T(n) = Θ(n log² n)

This is a popular trick question. n log n is bigger than n, but only by a log factor, not by n^ε, so it is not Case 3. With the basic (k = 0 only) version of the theorem, this recurrence is "not solvable by the Master Theorem". With the extended Case 2, the answer is Θ(n log² n).

Example 5: T(n) = 8T(n/2) + n² (Naive Divide and Conquer Matrix Multiplication)

a = 8, b = 2, d = 2
bᵈ = 4 < 8 = a          → Case 1
n^(log₂ 8) = n³

T(n) = Θ(n³)

Example 6: T(n) = 7T(n/2) + n² (Strassen)

a = 7, b = 2, d = 2
bᵈ = 4 < 7 = a          → Case 1

T(n) = Θ(n^(log₂ 7)) ≈ Θ(n^2.807)

Saving one multiplication out of eight changes the exponent from 3 to about 2.807. That is the whole point of Strassen's algorithm.

Example 7: T(n) = 2T(n/4) + √n

a = 2, b = 4, f(n) = n^(1/2)
n^(log₄ 2) = n^(1/2)
f(n) = Θ(n^(1/2))       → Case 2 with k = 0

T(n) = Θ(√n · log n)

Example 8: T(n) = √2 · T(n/2) + log n

a = √2, b = 2, f(n) = log n
n^(log₂ √2) = n^(1/2)
log n = O(n^(1/2 - ε)), e.g. ε = 0.25   → Case 1
(a log grows slower than any positive power of n)

T(n) = Θ(√n)

A Master Theorem Calculator

For the common case f(n) = Θ(nᵈ logᵏ n) with k ≥ 0, the whole decision fits in a few lines. This program applies the cases above:

import java.util.Locale;

class Main {

    // Solves T(n) = a T(n/b) + Theta(n^d * log^k n)  with a >= 1, b > 1, d >= 0, k >= 0
    static String solve(double a, double b, double d, int k) {

        double c = Math.log(a) / Math.log(b);      // critical exponent log_b(a)
        double eps = 1e-9;

        if (d < c - eps) {                         // Case 1: leaves dominate
            return "Case 1 -> Theta(" + power(c, 0) + ")";
        } else if (Math.abs(d - c) <= eps) {       // Case 2: all levels equal
            return "Case 2 -> Theta(" + power(d, k + 1) + ")";
        } else {                                   // Case 3: root dominates
            return "Case 3 -> Theta(" + power(d, k) + ")";
        }
    }

    // Formats n^e * log^k n
    static String power(double e, int k) {

        String n;
        if (Math.abs(e) < 1e-9) {
            n = "";
        } else if (Math.abs(e - 1) < 1e-9) {
            n = "n";
        } else if (Math.abs(e - Math.rint(e)) < 1e-9) {
            n = "n^" + (long) Math.rint(e);
        } else {
            n = "n^" + String.format(Locale.ROOT, "%.3f", e).replaceAll("0+$", "");
        }

        String log = (k == 0) ? "" : (k == 1 ? "log n" : "log^" + k + " n");

        if (n.isEmpty() && log.isEmpty()) return "1";
        if (n.isEmpty()) return log;
        if (log.isEmpty()) return n;
        return n + " " + log;
    }

    public static void main(String[] args) {

        System.out.println("T(n) = 9T(n/3) + n         : " + solve(9, 3, 1, 0));
        System.out.println("T(n) = T(2n/3) + 1         : " + solve(1, 1.5, 0, 0));
        System.out.println("T(n) = 3T(n/4) + n log n   : " + solve(3, 4, 1, 1));
        System.out.println("T(n) = 2T(n/2) + n log n   : " + solve(2, 2, 1, 1));
        System.out.println("T(n) = 8T(n/2) + n^2       : " + solve(8, 2, 2, 0));
        System.out.println("T(n) = 7T(n/2) + n^2       : " + solve(7, 2, 2, 0));
        System.out.println("T(n) = 4T(n/2) + n^2       : " + solve(4, 2, 2, 0));
        System.out.println("T(n) = 2T(n/4) + sqrt(n)   : " + solve(2, 4, 0.5, 0));
        System.out.println("T(n) = 3T(n/2) + n         : " + solve(3, 2, 1, 0));
    }
}

Output:

T(n) = 9T(n/3) + n         : Case 1 -> Theta(n^2)
T(n) = T(2n/3) + 1         : Case 2 -> Theta(log n)
T(n) = 3T(n/4) + n log n   : Case 3 -> Theta(n log n)
T(n) = 2T(n/2) + n log n   : Case 2 -> Theta(n log^2 n)
T(n) = 8T(n/2) + n^2       : Case 1 -> Theta(n^3)
T(n) = 7T(n/2) + n^2       : Case 1 -> Theta(n^2.807)
T(n) = 4T(n/2) + n^2       : Case 2 -> Theta(n^2 log n)
T(n) = 2T(n/4) + sqrt(n)   : Case 2 -> Theta(n^0.5 log n)
T(n) = 3T(n/2) + n         : Case 1 -> Theta(n^1.585)

The last line is Karatsuba multiplication. We compare exponents with a tiny tolerance (1e-9), because floating-point log values like log(9) / log(3) may not come out as exactly 2.0. In an exam, of course, you do this comparison by hand.


When the Master Theorem Does NOT Apply

This is a favourite multiple-choice question. The theorem cannot be used when:

Recurrence

Why it fails

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

Size shrinks by subtraction, not division (no n/b)

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

Subproblems have different sizes

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

a is not a constant

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

a < 1 (fewer than one subproblem makes no sense)

T(n) = 2T(n/2) - n

f(n) is negative

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

f(n) is smaller than n only by a log factor: not Case 1, and not Case 2 with k ≥ 0

T(n) = 2T(√n) + log n

Size shrinks to √n, not n/b (but see "Change of Variables" below)

For the n / log n case, an even more extended version of Case 2 is sometimes taught:

f(n) = Θ(n^(log_b a) · logᵏ n)

k > -1   → Θ(n^(log_b a) · logᵏ⁺¹ n)      (the usual Case 2)
k = -1   → Θ(n^(log_b a) · log log n)
k < -1   → Θ(n^(log_b a))

So T(n) = 2T(n/2) + n / log n  →  k = -1  →  Θ(n log log n)

You won't need this often, but it occasionally appears in GATE-style questions.


Decreasing Recurrences: T(n) = a·T(n - b) + f(n)

Many recursive functions reduce n by subtracting, not dividing. For these, there is a similar rule, sometimes called the Master Theorem for decreasing functions (or "subtract and conquer"):

T(n) = a · T(n - b) + f(n),    a > 0, b > 0, f(n) = O(nᵏ), k ≥ 0

a < 1   → O(nᵏ)
a = 1   → O(nᵏ⁺¹)
a > 1   → O(nᵏ · a^(n/b))

The intuition: with a = 1, there are about n/b levels, each doing up to nᵏ work. With a > 1, the number of calls multiplies by a at each of those n/b levels, which is exponential.

Recurrence

a, b, k

Result

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

1, 1, 0

O(n)

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

1, 1, 1

O(n²)

T(n) = T(n-2) + n²

1, 2, 2

O(n³)

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

2, 1, 0

O(2ⁿ)

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

2, 1, 1

O(n · 2ⁿ) (in fact Θ(2ⁿ))

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

3, 2, 0

O(3^(n/2)) ≈ O(1.732ⁿ)

Notice that this rule gives an upper bound (O), and it is not always tight. For T(n) = 2T(n-1) + n, the true answer is Θ(2ⁿ), because the work at the top levels is tiny compared with the 2ⁿ leaves. Back substitution gives the exact answer when you need it.

Naive Fibonacci: T(n) = T(n-1) + T(n-2) + 1

This one has two different subtractions, so the rule above doesn't apply directly. We can sandwich it:

Upper bound: T(n-2) ≤ T(n-1), so
             T(n) ≤ 2T(n-1) + 1      → O(2ⁿ)

Lower bound: T(n-1) ≥ T(n-2), so
             T(n) ≥ 2T(n-2) + 1      → Ω(2^(n/2)) ≈ Ω(1.414ⁿ)

The exact growth is Θ(φⁿ), where φ = (1 + √5) / 2 ≈ 1.618 is the golden ratio, the same number that the Fibonacci sequence itself grows by. We can watch this happen by counting the calls:

class Main {

    static long calls = 0;

    static long fib(int n) {
        calls++;
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {

        for (int n = 20; n <= 30; n += 5) {
            calls = 0;
            fib(n);
            System.out.println("n = " + n + "  calls = " + calls);
        }

        calls = 0;
        fib(29);
        long c29 = calls;

        calls = 0;
        fib(30);
        long c30 = calls;

        System.out.printf("calls(30) / calls(29) = %.4f%n", (double) c30 / c29);
    }
}

Output:

n = 20  calls = 21891
n = 25  calls = 242785
n = 30  calls = 2692537
calls(30) / calls(29) = 1.6180

Increasing n by just 5 multiplies the calls by about 11 (since 1.618⁵ ≈ 11.09), and the ratio between consecutive values is exactly the golden ratio to four decimal places. The exact count is 2·F(n+1) - 1, where F is the Fibonacci sequence. This exponential blow-up is the problem that Dynamic Programming, the next chapter, solves.


Change of Variables

Recurrences with √n look strange, but a substitution turns them into familiar ones. Let m = log₂ n, so n = 2ᵐ and √n = 2^(m/2).

Example: T(n) = 2T(√n) + log n

Substitute n = 2ᵐ:
    T(2ᵐ) = 2T(2^(m/2)) + m

Rename S(m) = T(2ᵐ):
    S(m) = 2S(m/2) + m          ← the Merge Sort recurrence!
    S(m) = Θ(m log m)

Go back (m = log n):
    T(n) = Θ(log n · log log n)

Two More (Frequently Asked)

T(n) = T(√n) + 1     →  S(m) = S(m/2) + 1   →  Θ(log m)  →  T(n) = Θ(log log n)
T(n) = 2T(√n) + 1    →  S(m) = 2S(m/2) + 1  →  Θ(m)      →  T(n) = Θ(log n)

The first one is worth remembering: taking the square root repeatedly reaches a constant in only log log n steps. For n = 2⁶⁴, that is 64 → 32 → 16 → 8 → 4 → 2 → 1 in the exponent, just 6 steps.


Which Method Should I Use?

Situation

Best method

T(n) = a·T(n/b) + f(n) with constant a, b

Master Theorem (fastest)

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

Back substitution, or the decreasing-function rule

Different subproblem sizes, like T(n/3) + T(2n/3)

Recursion tree

Sizes like √n or log n

Change of variables, then Master Theorem

You need a rigorous proof, or you already have a guess

Substitution (induction)

You need the exact closed form, not just Big O

Back substitution


Common Mistakes

1. Counting the subproblems wrong

return f(n/2) + f(n/2); is 2T(n/2), not T(n/2). Look at how many calls are actually executed.

2. Mixing up a and b

In T(n) = a·T(n/b) + f(n), a is how many calls and b is how much each call shrinks. For 3T(n/2), a = 3 and b = 2, so the critical exponent is log₂ 3, not log₃ 2.

3. Forgetting the "polynomially" in Cases 1 and 3

n log n is larger than n, but not by a factor of n^ε. So 2T(n/2) + n log n is Case 2 with k = 1 (answer Θ(n log² n)), not Case 3 (which would wrongly give Θ(n log n)).

4. Skipping the regularity check in Case 3

For polynomial f(n) it always holds, but for unusual functions (for example ones that oscillate, like n(2 - cos n)) it can fail, and then Case 3 cannot be used.

5. Using the Master Theorem on T(n - 1)

T(n) = T(n-1) + 1 is not of the form T(n/b). Forcing it in gives nonsense. Use back substitution: the answer is Θ(n).

6. "Proving" a bound with a growing constant

In the substitution method, ending with (c + 1)n when you assumed cn is not a proof. The constant must stay the same.

7. Forgetting the base case can matter for exact answers

The base case rarely changes the Big O, but it does change the exact formula. With T(1) = 1, Merge Sort's recurrence is n log₂ n + n. With T(1) = 0, it would be n log₂ n.


Interview and Exam Tips

  • Memorise the "big four" by heart: T(n/2) + 1 → log n, 2T(n/2) + 1 → n, 2T(n/2) + n → n log n, T(n-1) + n → n². Most interview recurrences are one of these.

  • For the Master Theorem, compare a with bᵈ. It's faster and less error-prone than computing logarithms.

  • When asked "what is the complexity of this recursive code?", say the recurrence out loud first, then solve it. Interviewers care about the reasoning.

  • For multiple choice, check the trick cases first: subtraction instead of division, unequal splits, n log n extra work, and √n sizes.

  • Remember that space for recursion is the maximum depth of the recursion tree, not the number of nodes. Merge Sort has 2n - 1 calls in total but a depth of only about log₂ n.

Practice: find the recurrence and the complexity for the recursive solutions of Pow(x, n) (LeetCode 50), Merge Sort (LeetCode 912), Search in a Binary Search Tree (LeetCode 700, for a balanced and for a skewed tree), and Tower of Hanoi (GeeksforGeeks). Then try the recurrence questions in the GATE CS previous year papers under "Algorithms: Asymptotic Analysis".


The Main Idea

A recurrence relation describes the running time of a recursive algorithm in terms of smaller inputs:

T(n) = (number of calls) × T(smaller size) + (extra work per call)

You can solve it with:

Back substitution  → expand until you see the pattern
Substitution       → guess, then prove by induction
Recursion tree     → add up the work level by level
Master Theorem     → T(n) = a·T(n/b) + f(n), compare f(n) with n^(log_b a)

The Master Theorem in one picture:

f(n) polynomially smaller than n^(log_b a)  → leaves win → Θ(n^(log_b a))
f(n) = Θ(n^(log_b a) · logᵏ n)              → tie        → Θ(n^(log_b a) · logᵏ⁺¹ n)
f(n) polynomially larger (+ regularity)     → root wins  → Θ(f(n))

And the results you will use most:

T(n) = T(n/2) + 1      → Θ(log n)       Binary Search
T(n) = 2T(n/2) + 1     → Θ(n)           Tree traversal, findMax
T(n) = 2T(n/2) + n     → Θ(n log n)     Merge Sort
T(n) = T(n-1) + n      → Θ(n²)          Quick Sort worst case
T(n) = 2T(n-1) + 1     → Θ(2ⁿ)          Tower of Hanoi
T(n) = T(n-1) + T(n-2) + 1 → Θ(1.618ⁿ)  Naive Fibonacci

To analyse any recursive algorithm, first write down how many calls it makes, how big they are, and how much extra work each call does. The recurrence then tells you everything about its running time.

The naive Fibonacci recurrence showed us that overlapping recursive calls can explode exponentially. In the next chapter, Dynamic Programming, we'll learn how to store and reuse those answers so that the same problem runs in linear time.