Recurrence Relations and Master Theorem

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.

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.

When Master Theorem fails (e.g., gap is not polynomial, or a/b are not constants), use:

1. 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).
2. 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).

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.

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

1. Substitution — guess the bound, prove it by induction. Good for verifying a suspected answer.
2. 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.
3. 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.