Master Theorem for Divide and Conquer
For T(n) = a.T(n/b) + f(n) with a>=1, b>1, compare f(n) with n^(log_b a) (the 'watershed').
- Case 1: if f(n) = O(n^(log_b a - e)) for some e>0, then T(n) = Theta(n^(log_b a)). (Leaves dominate.)
- Case 2: if f(n) = Theta(n^(log_b a)), then T(n) = Theta(n^(log_b a) . log n).
- Case 3: if f(n) = Omega(n^(log_b a + e)) AND regularity a.f(n/b) <= c.f(n) for c<1, then T(n) = Theta(f(n)). (Root dominates.)
Shortcut: compute c_crit = log_b a. Compare exponent of f. If f is polynomially smaller -> Case 1; equal (within log factors) -> Case 2; polynomially larger -> Case 3.
Standard Recurrences to Memorize
Lock these in for instant recall:
- T(n) = 2T(n/2) + n => Theta(n log n) [Merge sort, Case 2]
- T(n) = 2T(n/2) + 1 => Theta(n) [Case 1, log_b a = 1]
- T(n) = T(n/2) + 1 => Theta(log n) [Binary search]
- T(n) = T(n/2) + n => Theta(n) [Case 3]
- T(n) = 2T(n/2) + n log n => Theta(n log^2 n) [Master fails; use extended/tree]
- T(n) = 7T(n/2) + n^2 => Theta(n^(log2 7)) ~ Theta(n^2.81) [Strassen]
- T(n) = T(n-1) + 1 => Theta(n); T(n) = T(n-1) + n => Theta(n^2)
- T(n) = 2T(n-1) + 1 => Theta(2^n).
Master Theorem does NOT apply to subtract-and-conquer (n-1 form) or non-polynomial f gaps.
Substitution and Recursion Tree Methods
When Master Theorem fails (e.g., gap is not polynomial, or a/b are not constants), use:
- Recursion tree: sum work per level. Levels = log_b n. Work at level i = a^i . f(n/b^i). Sum the geometric/arithmetic series. If total dominated by root -> Theta(f(n)); by leaves -> Theta(n^(log_b a)); if equal per level -> multiply by number of levels (log factor).
- Substitution: guess the bound, prove by induction. Useful for T(n)=2T(n/2)+n which guesses cn log n.
Key trap: T(n) = 2T(n/2) + n/log n falls in the Master Theorem GAP between Case 1 and 2 (f is smaller than n by only a log factor, not polynomially). Recursion tree gives Theta(n log log n).
Recurrence Relations & Solving — Flashcards
Cover the answer, recall, then check. 12 GATE cards on solving recurrences.
Q1. Three standard methods to solve a recurrence.
A1. Substitution (guess + induction), recursion-tree, and the Master theorem (for divide-form). Akra–Bazzi generalises the Master theorem.
Q2. Solve T(n) = T(n−1) + O(1).
A2. Θ(n) — linear chain of constant work.
Q3. Solve T(n) = T(n−1) + O(n).
A3. Θ(n²) — sum 1+2+…+n. (This is worst-case quicksort / insertion sort.)
Q4. Solve T(n) = 2T(n−1) + O(1).
A4. Θ(2ⁿ) — subtract-and-conquer with branching (e.g. naïve Tower of Hanoi, exact 2ⁿ−1).
Q5. Solve T(n) = T(n/2) + O(1).
A5. Θ(log n) — halving with constant work (binary search).
Q6. Solve T(n) = T(√n) + O(1).
A6. Θ(log log n) — substitute n = 2^m so the size exponent halves each step.
Q7. Solve T(n) = 2T(n/2) + O(n).
A7. Θ(n log n) — Master Case 2 (merge sort).
Q8. Solve T(n) = T(n/3) + T(2n/3) + O(n).
A8. Θ(n log n) — unbalanced split but every level still costs Θ(n) and depth is Θ(log n).
Q9. Solve T(n) = T(n/2) + O(n) (geometric decrease).
A9. Θ(n) — Master Case 3; the top level's n dominates a geometric series.
Q10. Solve the Tower of Hanoi recurrence T(n) = 2T(n−1) + 1, T(1)=1.
A10. T(n) = 2ⁿ − 1 = Θ(2ⁿ).
Q11. Solve T(n) = √n · T(√n) + n.
A11. Θ(n log log n) — divide by n: S(n) = T(n)/n satisfies S(n) = S(√n) + 1 → Θ(log log n).
Q12. When must you avoid the Master theorem and use a recursion tree instead?
A12. Subtract-and-conquer forms T(n)=aT(n−b)+f, unequal subproblem sizes, non-constant a/b, or the gap/regularity failures of the Master theorem.
Recurrence Relations & Solving — Summary
Recurrences are how the running time of every recursive algorithm is expressed, so this topic is both directly tested (solve T(n) = …) and a prerequisite for sorting, searching and divide-and-conquer questions. GATE reliably includes at least one recurrence, and the non-Master-theorem forms (subtract-and-conquer, √n splits) are exactly where careless students lose the mark.
Three solving methods
- Substitution — guess the bound, prove it by induction. Good for verifying a suspected answer.
- Recursion tree — sum the work level-by-level; total = (work per level) × (number of levels), or a geometric series. Best for building intuition and for gap-cases.
- Master theorem — plug-and-play for T(n) = aT(n/b) + f(n) only.
Must-know closed forms
| Recurrence | Solution | Appears in |
|---|---|---|
| T(n−1)+O(1) | Θ(n) | linear scan |
| T(n−1)+O(n) | Θ(n²) | worst-case quicksort |
| 2T(n−1)+O(1) | Θ(2ⁿ) | Hanoi, naïve recursion |
| T(n/2)+O(1) | Θ(log n) | binary search |
| T(√n)+O(1) | Θ(log log n) | interval/vEB-style |
| 2T(n/2)+O(n) | Θ(n log n) | merge sort |
| T(n/3)+T(2n/3)+O(n) | Θ(n log n) | unbalanced split |
| T(n/2)+O(n) | Θ(n) | geometric decrease |
Exam Tricks & Tips
- 🎯 First classify divide (n/b) vs subtract (n−b). Divide → try Master theorem; subtract → recursion tree / expansion.
- 🎯 T(n)=aT(n−b)+O(1) is Θ(a^(n/b)) when a>1 — exponential; a=1 gives a polynomial from summing f.
- 🎯 √n recurrences: substitute n = 2^m to linearise, giving log log n behaviour.
- 🎯 Uneven splits that still cost Θ(n) per level and have Θ(log n) depth are Θ(n log n) — the imbalance does not change the class.
- 🎯 Geometric series shortcut: if work shrinks by a constant ratio each level, the total is Θ(top level); if it grows, Θ(bottom/leaves).
- ❌ Common mistake: forcing the Master theorem onto T(n)=2T(n−1)+1 and reporting a polynomial — it is exponential (Θ(2ⁿ)).
Expected exam pattern
Either a bare "solve the recurrence" MCQ or a recursive code snippet whose recurrence you derive and solve. Traps: subtract-form, √n split, and the Master theorem gap-case. Typically 1–2 marks.
Quick recap
Classify divide vs subtract. Memorise the eight closed forms above. Use the Master theorem only for aT(n/b)+f; otherwise expand a recursion tree and sum a geometric series. Substitute n=2^m for √n recurrences.