Master theorem

When you write a recursive algorithm like merge sort, you face a deceptively hard question: how fast does it actually run? The Master Theorem is a plug-and-play formula that answers this for the most common shape of divide-and-conquer recurrence, sparing you from drawing a full recursion tree every single time.

Definition: The Master Theorem provides closed-form solutions for recurrences of the form T(n) = a·T(n/b) + f(n), where a ≥ 1 subproblems are created, each of size n/b, with f(n) additional work done at each level to divide the input and combine the results.
Definition: The critical polynomial n^(log_b a) represents the total work done at the leaves of the recursion tree; it is the benchmark against which f(n) is compared to determine which case applies.

The structure of a divide-and-conquer recurrence

When an algorithm divides a problem of size n into a subproblems each of size n/b, and does f(n) work outside those recursive calls (splitting + merging), the recurrence T(n) = a·T(n/b) + f(n) captures the full cost. The total cost depends on whether the per-level combine work f(n) is small, comparable, or large relative to the leaf-level work.

To see why: at depth k in the recursion tree, there are a^k nodes, each handling a subproblem of size n/b^k. The total work at level k is a^k · f(n/b^k). The tree has log_b n levels. The work at the bottom level (the leaves) is a^(log_b n) = n^(log_b a) (by a logarithm identity). The Master Theorem compares the work at the top level f(n) against the work at the bottom level n^(log_b a):

• If the bottom (leaves) dominate → most work is at the leaves → T(n) = Θ(leaf work) = Θ(n^(log_b a)).
• If they are balanced → each level contributes equally → you pay for log n levels → T(n) = Θ(n^(log_b a) · log n) (roughly).
• If the top (combine step) dominates → most work is at the root → T(n) = Θ(f(n)).

The three cases — formal statements

Case 1 — Leaves dominate:
If f(n) = O(n^(log_b a − ε)) for some constant ε > 0 (f(n) is polynomially smaller than n^(log_b a)), then:
T(n) = Θ(n^(log_b a)).

Case 2 — Balanced:
If f(n) = Θ(n^(log_b a) · log^k n) for some k ≥ 0 (f(n) is asymptotically equal to n^(log_b a) up to logarithmic factors), then:
T(n) = Θ(n^(log_b a) · log^(k+1) n).
The most common sub-case is k = 0: if f(n) = Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) · log n).

Case 3 — Combine step dominates:
If f(n) = Ω(n^(log_b a + ε)) for some ε > 0 (f(n) is polynomially larger than n^(log_b a)), and the regularity condition a · f(n/b) ≤ c · f(n) for some c < 1 and all large n is satisfied, then:
T(n) = Θ(f(n)).

The regularity condition ensures the combine work truly concentrates at the top (each level's work is a fixed fraction of the level above, so the geometric series converges to the root). It is almost always satisfied by well-behaved functions, but you must check it in proofs.

Step-by-step method

1. Identify a, b, and f(n) from the recurrence.
2. Compute the critical exponent: log_b a.
3. Compare f(n) to n^(log_b a):
   • Is f(n) polynomially smaller (by n^ε)? → Case 1.
   • Are they equal (up to log factors)? → Case 2.
   • Is f(n) polynomially larger (by n^ε) and does regularity hold? → Case 3.
4. Apply the formula for the matching case.

Worked examples

Question 1: What is the time complexity of merge sort?
Recurrence: T(n) = 2T(n/2) + n.

Solution:
Step 1: a = 2, b = 2, f(n) = n.
Step 2: Critical polynomial: n^(log₂ 2) = n^1 = n.
Step 3: f(n) = n = Θ(n^1 · log⁰ n). This is Case 2 with k = 0.
Step 4: T(n) = Θ(n^1 · log^(0+1) n) = Θ(n log n).
Conclusion: T(n) = Θ(n log n).

---

Question 2: What is the complexity of binary search?
Recurrence: T(n) = T(n/2) + 1.

Solution:
Step 1: a = 1, b = 2, f(n) = 1.
Step 2: n^(log₂ 1) = n^0 = 1.
Step 3: f(n) = 1 = Θ(1) = Θ(n⁰ · log⁰ n). Case 2 with k = 0.
Step 4: T(n) = Θ(1 · log n) = Θ(log n).
Conclusion: T(n) = Θ(log n).

---

Question 3: Karatsuba's fast multiplication algorithm.
Recurrence: T(n) = 3T(n/2) + n.

Solution:
Step 1: a = 3, b = 2, f(n) = n.
Step 2: n^(log₂ 3) ≈ n^1.585.
Step 3: f(n) = n = O(n^(1.585 − ε)) for ε ≈ 0.585 > 0. This is Case 1.
Step 4: T(n) = Θ(n^log₂ 3) ≈ Θ(n^1.585).
Conclusion: T(n) = Θ(n^1.585) — significantly faster than the naïve O(n²) schoolbook multiplication.

---

Question 4 (GATE-style): T(n) = 4T(n/2) + n².
Solution:
Step 1: a = 4, b = 2, f(n) = n².
Step 2: n^(log₂ 4) = n^2.
Step 3: f(n) = n² = Θ(n² · log⁰ n). Case 2 with k = 0.
Step 4: T(n) = Θ(n² log n).
Conclusion: T(n) = Θ(n² log n).

---

Question 5 (Case 3 example): T(n) = 2T(n/2) + n².
Solution:
Step 1: a = 2, b = 2, f(n) = n².
Step 2: n^(log₂ 2) = n.
Step 3: f(n) = n² = Ω(n^(1+1)) for ε = 1. Check regularity: a·f(n/b) = 2·(n/2)² = n²/2 ≤ (1/2)·n² = c·f(n) with c = 0.5 < 1. ✓ Case 3.
Step 4: T(n) = Θ(f(n)) = Θ(n²).
Conclusion: T(n) = Θ(n²) — the expensive combine step dominates the recursion.

When the Master Theorem does NOT apply

The theorem has clear conditions; violating any one of them means you must fall back to other methods:

1. a is not a constant: T(n) = n·T(n/2) — the number of subproblems grows with n. Not covered.
2. b is not a constant greater than 1: T(n) = T(n−1) + 1 (decreasing by a constant, not a ratio). Not covered. This is the recurrence for linear search: solution is Θ(n) by substitution.
3. f(n) is not polynomially comparable to n^(log_b a): For example, f(n) = n/log n falls in a "gap" between Case 1 and Case 2 — the theorem gives no answer.
4. Regularity condition fails in Case 3: Rare for standard functions, but must be verified.

For these cases, use the substitution method (guess a form, verify by induction), the recursion-tree method (draw the tree, sum the geometric series level by level), or the more general Akra–Bazzi theorem (handles unequal subproblem sizes and more general f(n)).

Quick reference table

Algorithm	Recurrence	a, b, f(n)	Case	Complexity
Merge sort	T(n) = 2T(n/2) + n	2, 2, n	2	Θ(n log n)
Binary search	T(n) = T(n/2) + 1	1, 2, 1	2	Θ(log n)
Karatsuba	T(n) = 3T(n/2) + n	3, 2, n	1	Θ(n^1.585)
Strassen's matrix mult.	T(n) = 7T(n/2) + n²	7, 2, n²	1	Θ(n^log₂7) ≈ Θ(n^2.807)
Binary tree traversal	T(n) = 2T(n/2) + 1	2, 2, 1	1	Θ(n)
Quicksort (average)	T(n) = 2T(n/2) + n	2, 2, n	2	Θ(n log n)

Why it matters: In GATE CSE, algorithm analysis carries significant weightage — typically 5–8 marks on recurrences and complexity. In campus placement tests, reading off T(n) from a recurrence in under 30 seconds is an expected skill. The Master Theorem is the most efficient way to do this.

Real-world example: A logistics app sorts millions of delivery addresses by pincode using merge sort. The Master Theorem tells the engineer the cost is Θ(n log n) — so doubling the number of deliveries roughly doubles the time plus a small log factor, not quadruples it. This predictability lets the team promise consistent performance during Diwali or Big Billion Day order spikes, when deliveries could surge from 1 million to 5 million in a day. Engineers who know the Master Theorem can model infrastructure costs before writing a line of code.

Common misconception: "The Master Theorem solves all recurrences." It does not. It handles only the specific form T(n) = a·T(n/b) + f(n) with constant a and b > 1, when f(n) satisfies the growth conditions for one of the three cases. T(n) = T(n−1) + 1 (linear search), T(n) = T(√n) + 1 (a real GATE favourite — solution is Θ(log log n) by substitution), and T(n) = T(n/2) + T(n/3) + n (non-uniform splits) all fall outside the theorem. Blindly applying the Master Theorem to these leads to wrong answers; recognising when to switch methods is what separates a strong student from a mechanical one.

Understanding how algorithms scale is the difference between writing code that runs in a second and code that runs overnight — asymptotic analysis is the mathematical language of that difference.

Definition: Asymptotic analysis describes how the running time or memory usage of an algorithm grows as the input size n approaches infinity, ignoring constant factors and lower-order terms.

Definition: Big O notation — f(n) = O(g(n)) means there exist constants c > 0 and n₀ ≥ 1 such that f(n) ≤ c·g(n) for all n ≥ n₀. This expresses an upper bound on growth.

Definition: Big Omega — f(n) = Ω(g(n)) means f(n) ≥ c·g(n) for all n ≥ n₀. This expresses a lower bound.

Definition: Big Theta — f(n) = Θ(g(n)) means f = O(g) AND f = Ω(g). This is a tight bound — the function grows at exactly the same rate as g.

The Three Notations — A Precise Comparison

Common misconception: O-notation is often described as "the worst case." This is imprecise. Big O is an upper bound on growth — it can describe best, average, or worst case depending on what you apply it to. For example, insertion sort is O(n) in the best case (sorted input) and O(n²) in the worst case. Both are correct O statements about different scenarios.

Common Growth Classes — Ordered Slowest to Fastest

Complexity	Name	Representative Algorithm
O(1)	Constant	Hash table lookup, array access by index
O(log log n)	Log-log	Some advanced data structures
O(log n)	Logarithmic	Binary search, balanced BST operations
O(√n)	Square root	Naive primality check (trial division to √n)
O(n)	Linear	Linear scan of array, counting sort
O(n log n)	Linearithmic	Merge sort, heap sort, FFT
O(n²)	Quadratic	Bubble sort, insertion sort, selection sort
O(n³)	Cubic	Floyd–Warshall, naïve matrix multiplication
O(2ⁿ)	Exponential	Subset enumeration, TSP brute force
O(n!)	Factorial	Brute-force permutations

Why it matters: For n = 10⁶ (a common data size), O(n log n) ≈ 2 × 10⁷ operations (fast); O(n²) = 10¹² operations (would take hours). Choosing the right algorithm is not a theoretical exercise — it determines whether a product is usable.

Real-world example: IRCTC processes millions of ticket searches. Binary search (O(log n)) over a sorted price table returns results in microseconds; a linear scan (O(n)) over 10 million records would take noticeably longer. The difference becomes critical under peak Diwali traffic.

Rules for Manipulating O-notation

Sum rule: O(f) + O(g) = O(max(f, g)).
Example: O(n²) + O(n log n) = O(n²) — the dominant term wins.

Product rule: O(f) × O(g) = O(f·g).
Example: a nested loop over n elements repeated log n times = O(n log n).

Constant factors: O(c·f) = O(f) for any positive constant c.
Example: O(3n²) = O(n²) — you drop the 3.

Log base is irrelevant: log₂ n and log₁₀ n differ by a constant factor (log₂ n = log₁₀ n / log₁₀ 2), so O(log₂ n) = O(log₁₀ n) = O(log n).

Exponential bases do matter: O(2ⁿ) ≠ O(3ⁿ) because 3ⁿ = (3/2)ⁿ × 2ⁿ and (3/2)ⁿ → ∞, not a constant.

Recurrence Relations and the Master Theorem

Many recursive algorithms produce recurrences of the form T(n) = aT(n/b) + f(n).

Master Theorem (for T(n) = aT(n/b) + n^k):

• If k < log_b(a): T(n) = Θ(n^{log_b a}) — recursive cost dominates.
• If k = log_b(a): T(n) = Θ(n^k log n) — even split.
• If k > log_b(a): T(n) = Θ(n^k) — root cost dominates.

Recurrence	Algorithm	Solution
T(n) = T(n−1) + 1	Linear recursion	O(n)
T(n) = T(n−1) + n	Selection sort	O(n²)
T(n) = T(n/2) + 1	Binary search	O(log n)
T(n) = T(n/2) + n	Quickselect (avg)	O(n)
T(n) = 2T(n/2) + n	Merge sort	O(n log n)
T(n) = 7T(n/2) + n²	Strassen matrix mult	O(n^{log₂ 7}) ≈ O(n^2.807)

Best, Average, and Worst Case

Algorithm	Best	Average	Worst
Linear search	O(1)	O(n/2) = O(n)	O(n)
Binary search	O(1)	O(log n)	O(log n)
Bubble sort	O(n)	O(n²)	O(n²)
Insertion sort	O(n)	O(n²)	O(n²)
Quick sort	O(n log n)	O(n log n)	O(n²)
Merge sort	O(n log n)	O(n log n)	O(n log n)
Hash table (good hash)	O(1)	O(1)	O(n)

Bubble sort's best case is O(n) only if you implement the early-exit optimisation (stop if no swaps occur in a full pass).

Time vs Space Complexity

Every algorithm has both a time complexity and a space complexity (auxiliary memory). Sometimes you trade one for the other:

• Merge sort: O(n log n) time, O(n) space — needs extra array.
• Quick sort: O(n log n) average time, O(log n) space (recursion stack depth).
• In-place sorting (heap sort): O(n log n) time, O(1) space.

Amortised Analysis

Some operations are individually expensive but amortised over many calls they are cheap. Definition: Amortised complexity is the average cost per operation over the worst-case sequence of n operations.

Classic example: A Python list (dynamic array). append() is usually O(1). When the internal buffer is full, a resize copies all n elements — O(n). But resizing doubles the capacity each time, so resizes happen at sizes 1, 2, 4, 8, … Total copy work after n appends ≤ n + n/2 + n/4 + … ≤ 2n. Thus n appends cost O(2n) total → O(1) amortised per append.

Practical Thresholds

n	Feasible complexity
≤ 10	O(n!) or O(2ⁿ)
≤ 20	O(2ⁿ)
≤ 500	O(n³)
≤ 5000	O(n²)
≤ 10⁶	O(n log n)
≤ 10⁸	O(n)
Any	O(log n), O(1)

Cover the answer, recall, then check. 12 GATE cards on the Master theorem.

Q1. State the Master theorem's recurrence form.
A1. T(n) = a·T(n/b) + f(n), with a ≥ 1, b > 1 constants and f(n) asymptotically positive. Compare f(n) with the watershed n^(log_b a).

Q2. What is the "watershed" or critical exponent?
A2. n^(log_b a). The whole method compares f(n) against it.

Q3. Case 1 condition and result.
A3. If f(n) = O(n^(log_b a − ε)) for some ε > 0, then T(n) = Θ(n^(log_b a)). (Leaves dominate.)

Q4. Case 2 condition and result.
A4. If f(n) = Θ(n^(log_b a) · logᵏ n) with k ≥ 0, then T(n) = Θ(n^(log_b a) · log^(k+1) n). (Balanced.)

Q5. Case 3 condition and result.
A5. If f(n) = Ω(n^(log_b a + ε)) AND the regularity condition a·f(n/b) ≤ c·f(n) for some c < 1 holds, then T(n) = Θ(f(n)). (Root dominates.)

Q6. Solve T(n) = 2T(n/2) + Θ(n) (merge sort).
A6. a=2, b=2, log_b a = 1; f = n = Θ(n¹) → Case 2 (k=0) → Θ(n log n).

Q7. Solve T(n) = T(n/2) + Θ(1) (binary search).
A7. a=1, b=2, log_b a = 0; f = Θ(1) = Θ(n⁰) → Case 2 → Θ(log n).

Q8. Solve T(n) = 4T(n/2) + n.
A8. log_2 4 = 2; f = n = O(n^(2−ε)) → Case 1 → Θ(n²).

Q9. Solve T(n) = 2T(n/2) + n².
A9. log_2 2 = 1; f = n² = Ω(n^(1+ε)), regularity 2·(n/2)² = n²/2 ≤ c·n² holds → Case 3 → Θ(n²).

Q10. Solve T(n) = 7T(n/2) + Θ(n²) (Strassen).
A10. log_2 7 ≈ 2.807; f = n² = O(n^(2.807−ε)) → Case 1 → Θ(n^log₂7) ≈ Θ(n^2.807).

Q11. Why does Master theorem fail on T(n) = 2T(n/2) + n/log n?
A11. f = n/log n is smaller than n but by only a log factor, not a polynomial factor n^ε — it falls in the gap between Case 1 and Case 2. (Answer via recursion tree is Θ(n log log n).)

Q12. Two other reasons the Master theorem cannot be applied.
A12. (i) Case 3's regularity condition fails; (ii) a or b is not a constant, b ≤ 1, or f(n) is not positive. Also fails when subproblem sizes differ (use Akra–Bazzi).

The Master theorem is the single highest-yield tool for divide-and-conquer recurrences, and GATE asks it almost every year — either directly ("solve T(n) = …") or embedded inside a sorting/searching complexity question. Learn the three cases and the watershed and you convert a page of algebra into a 20-second answer.

The recurrence and the watershed

For T(n) = a·T(n/b) + f(n) with a ≥ 1, b > 1 constant, compute the critical exponent n^(log_b a) and compare f(n) to it.

Case	Condition on f(n)	Result
1 (leaves win)	f = O(n^(log_b a − ε))	Θ(n^(log_b a))
2 (balanced)	f = Θ(n^(log_b a)·logᵏn), k≥0	Θ(n^(log_b a)·log^(k+1)n)
3 (root wins)	f = Ω(n^(log_b a + ε)) + regularity	Θ(f(n))

Worked anchors (memorise):

Recurrence	log_b a	Case	Solution
2T(n/2)+n	1	2	Θ(n log n)
T(n/2)+1	0	2	Θ(log n)
4T(n/2)+n	2	1	Θ(n²)
2T(n/2)+n²	1	3	Θ(n²)
7T(n/2)+n²	2.807	1	Θ(n^2.807)
3T(n/2)+n	1.585	1	Θ(n^1.585)

Exam Tricks & Tips

• 🎯 Compute log_b a FIRST, then just ask: is f polynomially smaller (Case 1), equal-ish (Case 2), or polynomially larger (Case 3)?
• 🎯 "Polynomially" is the keyword — the ε gap must be a factor of n^ε, not just a log. A log-factor difference means the theorem does not apply.
• 🎯 Case 2 with logs: if f = Θ(n^(log_b a)·logᵏn), the answer gains ONE extra log: log^(k+1)n.
• 🎯 Always verify regularity for Case 3 — for polynomial f it holds automatically, but examiners plant cases where it does not.
• 🎯 Strassen anchor: 7T(n/2)+n² = Θ(n^log₂7) ≈ n^2.807 — a favourite MCQ.
• ❌ Common mistake: applying the theorem to subtract-and-conquer forms like T(n)=2T(n−1)+1. The Master theorem is ONLY for the n/b (divide) form; use a recursion tree/substitution for n−b.

Expected exam pattern

"Solve the recurrence" MCQs, or a code snippet whose recurrence you must derive then solve. Watch for the deliberate gap-case (n/log n) or regularity trap. Usually 1–2 marks.

Quick recap

T(n) = aT(n/b) + f(n): compare f to n^(log_b a). Smaller → Θ(n^(log_b a)); equal → add a log; larger (+regularity) → Θ(f). Only for divide-form recurrences; watch the polynomial-gap and regularity traps.

Key formulas

For T(n) = a·T(n/b) + f(n), a ≥ 1, b > 1, compare f(n) with n^(log_b a):

• Case 1: if f(n) = O(n^(log_b a − ε)) then T(n) = Θ(n^(log_b a)).
• Case 2: if f(n) = Θ(n^(log_b a)) then T(n) = Θ(n^(log_b a) · log n).
• Case 3: if f(n) = Ω(n^(log_b a + ε)) and a·f(n/b) ≤ c·f(n) (regularity), then T(n) = Θ(f(n)).
• Critical exponent: c* = log_b a.
• Common results: T(n)=2T(n/2)+n ⇒ Θ(n log n); T(n)=T(n/2)+1 ⇒ Θ(log n); T(n)=2T(n/2)+1 ⇒ Θ(n); T(n)=4T(n/2)+n ⇒ Θ(n²).
• Extended (Case 2 general): f(n)=Θ(n^(log_b a) logᵏn) ⇒ T(n)=Θ(n^(log_b a) log^{k+1} n).

Usage: compute log_b a first, then classify f(n) relative to it.

Worked Example

Problem: Use the Master theorem to solve the recurrences (a) T(n) = 2T(n/2) + n and (b) T(n) = 4T(n/2) + n.

Solution:
The Master theorem for T(n) = a·T(n/b) + f(n) compares f(n) with n^(log_b a).

(a) T(n) = 2T(n/2) + n: here a = 2, b = 2, so n^(log_b a) = n^(log₂2) = n¹ = n.
Compare f(n) = n with n^(log_b a) = n: they are the same order, f(n) = Θ(n^(log_b a)).
This is Case 2, which gives T(n) = Θ(n^(log_b a)·log n) = Θ(n·log n).
(This is exactly the merge-sort recurrence.)

(b) T(n) = 4T(n/2) + n: here a = 4, b = 2, so n^(log_b a) = n^(log₂4) = n².
Compare f(n) = n with n²: f(n) = O(n^(2 − ε)) for ε = 1, so f is polynomially smaller.
This is Case 1, which gives T(n) = Θ(n^(log_b a)) = Θ(n²).

Answer: (a) T(n) = Θ(n log n); (b) T(n) = Θ(n²).