Master Theorem questions become mechanical when you compare the correct two functions. The trouble begins when a logarithmic gap is mistaken for a polynomial gap, or Case 3 is chosen without its regularity check. This guide builds the decision from the recurrence and then tests it on the boundary cases.
Start with the critical term
The theorem applies to
T(n) = aT(n/b) + f(n),
where a >= 1 and b > 1 are constants, and f(n) is asymptotically positive. The recursion tree has a^(log_b n) = n^(log_b a) leaves. Define the critical exponent d = log_b a, so the critical term is n^d.
The whole classification compares f(n) with n^d. The related time complexity and asymptotic notation guide is useful if the difference between polynomial and logarithmic growth is not yet automatic.
The three Master Theorem cases
Case | Comparison with | Extra condition | Result |
|---|---|---|---|
1 |
| None |
|
2 |
| None |
|
3 |
|
|
|
The e > 0 condition says that the gap must be polynomial. A factor of log n grows, but it is smaller than n^e for every fixed positive e.
Case 1 worked: leaves dominate
Take T(n) = 8T(n/2) + n^2.
a = 8,b = 2, sod = log_2 8 = 3.The critical term is
n^3.f(n) = n^2 = O(n^(3-1)), soe = 1works.Case 1 gives
T(n) = Theta(n^3).
Another quick classification is T(n) = 3T(n/2) + n. Here d = log_2 3, about 1.585. Since n is polynomially smaller than n^1.585, the answer is Theta(n^(log_2 3)).
Case 2 worked: each level ties
For T(n) = 2T(n/2) + n, d = log_2 2 = 1, so f(n) = n exactly matches n^d. There are log n levels with Theta(n) work per level. The result is Theta(n log n).
For T(n) = T(n/2) + 1, d = log_2 1 = 0, and n^0 = 1. Again there is a tie, giving Theta(log n).
A common extended form covers f(n) = Theta(n^d log^k n) for k >= 0, producing Theta(n^d log^(k+1) n). Thus T(n) = 2T(n/2) + n log n has d = 1, k = 1, and answer Theta(n log^2 n). This is not basic Case 3 because the upward gap is only logarithmic.
Case 3 worked: check regularity
Consider T(n) = 2T(n/2) + n^2.
d = 1, so the critical term isn.n^2 = Omega(n^(1+1)), so the polynomial-gap test passes withe = 1.Let
f(n) = n^2. Thena f(n/b) = 2(n/2)^2 = n^2/2.Choose
c = 1/2, which is below 1. Regularity holds.
Therefore T(n) = Theta(n^2). For a plain power f(n) = n^k with k > d, the ratio is a/b^k, which is below 1. Irregular or oscillating functions still need an explicit check.
Recurrences the theorem cannot handle
First test the shape. T(n) = T(n-1) + n shrinks by subtraction, not by a constant division factor. Direct summation gives 1 + 2 + ... + n = n(n+1)/2 = Theta(n^2), but the Master Theorem did not produce it.
Now take T(n) = 2T(n/2) + n/log n. The critical term is n, yet n/log n is not polynomially smaller than n. There is no fixed e > 0 for which n/log n = O(n^(1-e)). It also falls outside the stated extended Case 2 because that version requires k >= 0, while here k = -1.
A recursion-tree check finds the actual bound. At level i, total non-recursive work is
2^i [(n/2^i) / log(n/2^i)] = n / (log n - i).
Summing from the root toward the leaves gives n(1/1 + 1/2 + ... + 1/log n) = Theta(n log log n). The bound is valid, but it came from a tree sum, not a Master Theorem case.
Regularity can also fail. In T(n) = T(n/2) + n(2 - cos n), the additive term is polynomially larger than the critical constant, but its oscillation prevents one constant c < 1 from satisfying f(n/2) <= c f(n) for all sufficiently large n. Case 3 cannot be claimed.
Solved recurrence classification drill
Recurrence | Critical term | Classification | Answer |
|---|---|---|---|
|
| Case 1 |
|
|
| Case 2 |
|
|
| Case 3, |
|
|
| Case 1 |
|
|
| Case 2 |
|
|
| Case 1 |
|
|
| Case 1 |
|
|
| Case 2 |
|
For the third row, 4(n/2)^3 = n^3/2, so the displayed regularity constant is correct. For T(2n/3), write the subproblem as n/(3/2), giving b = 3/2 and d = 0.
How GATE tests recurrence classification
Expect a tight-bound choice, a numerical exponent, or a statement asking whether the theorem applies. The trap answer is often a plausible bound reached through an invalid case. About 1,100 published Algorithm questions in the KnowledgeGate bank provide broader practice, including data structures questions that exercise the same asymptotic language.
Confirm current paper instructions on the official GATE portal of the organising IIT.
The short version
Compute d = log_b a, compare f(n) with n^d, and demand a polynomial gap for Cases 1 or 3. Check regularity before claiming Case 3. If a log-sized gap or the recurrence shape falls outside the theorem, switch to a recursion tree or substitution.
Use the GATE Test Series to practise classification under a clock, and the GATE category page to connect this drill to the rest of your subject plan. Then reclassify the table without looking at its last two columns.
