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

Updated 15 Nov 20265 min read
Master Theorem for GATE CS: Cases, Worked Recurrences and Exam Traps

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 n^p

Extra check

Result

1

f(n) = O(n^(p-epsilon)), some epsilon > 0

Polynomially smaller

Theta(n^p)

2

f(n) = Theta(n^p)

Basic balanced form

Theta(n^p log n)

3

f(n) = Omega(n^(p+epsilon)), some epsilon > 0

a f(n/b) <= c f(n) for some c < 1 eventually

Theta(f(n))

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

Recursion tree for T(n)=3T(n/3)+2n, with four costs of 54 summing to T(27)=216.

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

T(n) = 9T(n/3) + n

p = log_3 9 = 2. Since n = O(n^(2-1)), choose epsilon = 1. Case 1 gives Theta(n^2).

The recursive leaves dominate the linear combine work.

T(n) = 4T(n/2) + n^3

p = log_2 4 = 2. Since n^3 = Omega(n^(2+1)), choose epsilon = 1. Case 3 gives Theta(n^3).

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) + n has unequal subproblem sizes.

  • T(n) = 2T(n-1) + 1 shrinks by subtraction, not by a constant factor.

  • T(n) = 4T(n/2) + n^2 log n lies 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.

Decision flow for the Master Theorem: test for equal-sized subproblems, compare f(n) with n^(log_b a), then check Case 3 regularity.

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 a and b

Read coefficient, then divisor.

Compare f(n) with a/b

Compare it with n^p.

Treat a log factor as a polynomial gap

Use the declared theorem version.

Omit Case 3 regularity

Calculate a f(n/b).

Report only a case number

State the final Theta bound.

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.