Master Theorem for GATE CS: Cases, Worked Recurrences and Exam Traps
Learn a repeatable way to classify divide-and-conquer recurrences. Work through all three cases, exact arithmetic, non-applicable forms, and common traps.
KnowledgeGate Team
Exam prep & CS education

Students often remember the three Master Theorem cases yet compare the wrong quantities. Another common mistake is forcing the theorem onto a recurrence whose subproblems are not equally sized. For GATE CS preparation, use a fixed routine: read a, b, and f(n), calculate n^(log_b a), check for a polynomial gap, and only then name the case. That order turns classification into a repeatable Algorithms method instead of a memory test.
Master Theorem recurrence: read a, b, and f(n) first
The standard form is T(n) = aT(n/b) + f(n). Here, a >= 1 is the number of equal-sized recursive subproblems, every subproblem has size n/b for a constant b > 1, and f(n) is the non-recursive work. Floors and ceilings usually preserve the asymptotic result.
Set p = log_b a. The critical work is n^p: level i has a^i nodes of size n/b^i, and the leaf count is Theta(n^p).
For T(n) = 3T(n/2) + 2n + 5, read a = 3, b = 2, and f(n) = 2n + 5 = Theta(n). Do not swap the coefficient and divisor to get a = 2, b = 3.
Master Theorem cases: compare with a polynomial gap
The basic three-case statement has Cases 1 and 3 for polynomial gaps and a balanced Case 2. Logarithmic factors need the extended Case 2, so state which version you are applying before you use it.
Case | Comparison with | Extra check | Result |
|---|---|---|---|
1 |
| Polynomially smaller |
|
2 |
| Basic balanced form |
|
3 |
|
|
|
Leaves dominate in Case 1, all levels balance in Case 2, and root-side work dominates in Case 3. A logarithmic factor alone does not create the polynomial gap required by basic Cases 1 or 3.
Master Theorem worked example: T(n) = 3T(n/3) + 2n

Here a = 3, b = 3, and p = log_3 3 = 1, so n^p = n. Since f(n) = 2n = Theta(n), basic Case 2 gives T(n) = Theta(n log n).
Take n = 27 and T(1) = 2. The recursion tree has three internal levels. Level 0 costs 1 x 54 = 54; level 1 costs 3 x 18 = 54; and level 2 costs 9 x 6 = 54. The 27 leaves contribute 27 x T(1) = 54, so T(27) = 54 + 54 + 54 + 54 = 216.
Direct expansion gives T(3) = 12 and T(9) = 54 before T(27) = 216. This independently checks every internal level and the base-cost leaves.
For powers of three, substitution gives T(n) = 2n log_3 n + 2n. At 27, this is 2 x 27 x 3 + 2 x 27 = 216. The exact value depends on the stated base cost; Theta(n log n) is the asymptotic answer.
Master Theorem worked examples for Case 1 and Case 3
Recurrence | Classification | Why the final order arises |
|---|---|---|
|
| The recursive leaves dominate the linear combine work. |
|
| The cubic combine work dominates after regularity holds. |
For Case 3, verify regularity: a f(n/b) = 4(n/2)^3 = n^3/2 <= (1/2)n^3, so c = 1/2. The Case 1 recurrence finishes at Theta(n^2), while the Case 3 recurrence finishes at Theta(n^3); each answer matches the side that dominates. The earlier Time complexity and asymptotic notation: Big-O, Theta and Omega explained owns the broader framework of notation, growth ordering, and loop analysis. The narrower task here is choosing a Master Theorem case, checking regularity, and rejecting forms outside the theorem.
When the basic Master Theorem does not apply
Three forms fail three different tests:
T(n) = T(n/2) + T(n/3) + nhas unequal subproblem sizes.T(n) = 2T(n-1) + 1shrinks by subtraction, not by a constant factor.T(n) = 4T(n/2) + n^2 log nlies on a logarithmic boundary outside the basic statement.
For the third, the critical exponent is p = log_2 4 = 2, and the extended theorem or a recursion tree gives Theta(n^2 log^2 n). It is not basic Case 3 because n^2 log n is not polynomially larger than n^2. Use Akra-Bazzi for the unequal-size recurrence, direct expansion for the subtraction recurrence, and the extended theorem for the logarithmic boundary.

Master Theorem exam traps and a timed classification routine
Use five steps: normalise; identify a, b, and f(n); compute p = log_b a; test the polynomial gap; verify regularity for Case 3. If the form fails, stop.
Trap | Fix |
|---|---|
Swap | Read coefficient, then divisor. |
Compare | Compare it with |
Treat a log factor as a polynomial gap | Use the declared theorem version. |
Omit Case 3 regularity | Calculate |
Report only a case number | State the final |
Return to 3T(n/2) + 2n + 5. Here p = log_2 3. Since 1 < log_2 3, choose any 0 < epsilon < log_2 3 - 1. Case 1 gives Theta(n^(log_2 3)). Practise the routine under test conditions with the GATE Test Series.
Master Theorem short version and next step
Compare f(n) with n^(log_b a). Demand a polynomial gap for Cases 1 and 3, and check regularity for Case 3. Re-solve the four valid recurrences without looking, then explain aloud why each case applies and why every counterexample fails the basic theorem. Once you can do that cleanly, GATE Guidance by Sanchit Sir is an optional structured route across the wider subjects.
Keep learning
Master Theorem for GATE: All Cases, Boundary Traps and Solved Recurrences
Classify divide-and-conquer recurrences through one comparison, verify the regularity condition, and recognise the log-gap recurrences that need another method.
Algorithm Analysis: Asymptotic Notation, Recurrences and Worked Examples for GATE CS
Build algorithm-analysis skill from first principles: count operations, compare growth rates, solve recurrences and understand amortized cost through checked examples.
Big Data Systems for GATE CS: CAP Theorem, Sharding and MapReduce with Worked Examples
See what changes when a database spreads across machines. Build a clear mental model of shards, replicas, CAP choices, quorums, MapReduce and NoSQL.
Master Theorem Interview Questions: Recurrence Traces and Model Answers
Learn to explain the Master Theorem aloud, trace an exact recurrence, distinguish its three cases, derive a recurrence from code and recognise when the theorem does not apply.





