Master Theorem for GATE: All Cases, Boundary Traps and Solved Recurrences

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. Both failures come from the same skipped step: the critical exponent has to be pinned down before f(n) is looked at.

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

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.

1. a = 8, b = 2, so d = log_2 8 = 3.

2. The critical term is n^3.

3. f(n) = n^2 = O(n^(3-1)), so e = 1 works.

4. 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).

Keep a = 8 and b = 2 from the Case 1 example, but raise the combine cost to f(n) = n^3. Now d = 3 and n^3 matches n^d exactly, so the tie gives T(n) = Theta(n^3 log n). The same subproblem count with a heavier combine costs one extra log factor.

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.

1. d = 1, so the critical term is n.

2. n^2 = Omega(n^(1+1)), so the polynomial-gap test passes with e = 1.

3. Let f(n) = n^2. Then a f(n/b) = 2(n/2)^2 = n^2/2.

4. 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 over all the levels 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

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 at all. The trap answer is usually a plausible bound reached through an invalid case, so it sits in the option list looking correct.

Work T(n) = 4T(n/2) + n^2 log n the way an examiner sets it. Here d = 2, and n^2 log n is larger than n^2, so Case 3 looks inviting and Theta(n^2 log n) is the option most attempts pick. The polynomial-gap test refuses it: n^2 log n is not Omega(n^(2+e)) for any fixed e > 0, because log n loses to n^e. It is the extended Case 2 with k = 1, so the bound is Theta(n^2 log^2 n). Answer and distractor differ by exactly one log factor, which is what makes that option list dangerous.

Option lists also mix notations. n^(log_2 7) and n^2.81 are the same bound written two ways, since log_2 7 = 2.807...; row four of the drill above is exactly that recurrence. Settle the case first, then match it to whichever form the paper prints.

Around 1,200 Algorithm questions in the KnowledgeGate question bank give 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.