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 |
|
|
One call on |
|
|
Two calls on |
|
|
One call on |
|
|
Two calls on |
|
|
Two calls on |
|
|
One call on |
|
|
Calls on |
|
|
Two details trip students up:
Count calls, not lines.
return f(n/2) + f(n/2);makes two calls, so it is2T(n/2). Storing the result in a variable and reusing it makes itT(n/2). This is exactly the fast power trick from the Divide and Conquer chapter.The extra work matters.
T(n) = 2T(n/2) + 1isΘ(n), whileT(n) = 2T(n/2) + nisΘ(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ⁿ)
Example 3: T(n) = T(n/2) + 1, with T(1) = 1 (Binary Search)
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:
Guess the form of the answer (from experience, or from a recursion tree).
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 |
|
| Leaves |
2 |
|
| All levels equally |
3 |
|
| Root |
A few notes on these conditions:
"Polynomially" smaller or larger means by a factor of
n^ε. Being smaller or larger by only alog nfactor is not enough for Case 1 or Case 3. Whenf(n)is larger by a log factor (liken log nagainstn), the extended Case 2 below handles it. When it is smaller by a log factor (liken / log nagainstn), 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). Thelogᵏform shown here is the more general version, and it covers recurrences like2T(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ᵈornᵈ logᵏ n, it is automatically true wheneverd > 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 |
|---|---|
| Size shrinks by subtraction, not division (no |
| Subproblems have different sizes |
|
|
|
|
|
|
|
|
| Size shrinks to |
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 |
|---|---|---|
| 1, 1, 0 |
|
| 1, 1, 1 |
|
| 1, 2, 2 |
|
| 2, 1, 0 |
|
| 2, 1, 1 |
|
| 3, 2, 0 |
|
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 |
|---|---|
| Master Theorem (fastest) |
| Back substitution, or the decreasing-function rule |
Different subproblem sizes, like | Recursion tree |
Sizes like | 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
awithbᵈ. 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 nextra work, and√nsizes.Remember that space for recursion is the maximum depth of the recursion tree, not the number of nodes. Merge Sort has
2n - 1calls in total but a depth of only aboutlog₂ 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.