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.
KnowledgeGate Team
Exam prep & CS education

Candidates often remember three Master Theorem case labels but swap a and b. Others compare f(n) against the wrong power or force the theorem onto a recurrence it cannot solve. Work through the n=8 trace, compare the three cases, translate code into a recurrence and practise concise model answers.
What does the Master Theorem say? Give the 30-second model answer
Start with T(n) = aT(n/b) + f(n), where a >= 1 and b > 1 are constants, and f(n) is positive asymptotic non-recursive work. Here, a is the number of equal recursive subproblems, while n/b is each subproblem's size.
Compute the benchmark p = log_b(a), which makes the recursive leaf scale n^p. Then follow a five-part protocol: identify a, b and f(n); compute p; compare f(n) with n^p; verify the required polynomial-gap or regularity condition; and state a tight Theta bound with the dominating recursion-tree level. Revise Big-O, Omega and Theta first through the time-complexity and asymptotic-notation guide. Do not settle for Big-O when the theorem supports Theta.
Solve T(n) = 4T(n/2) + n^2 and prove the answer with n = 8
The model answer is direct. Here a=4, b=2, f(n)=n^2 and p=log_2(4)=2. Therefore, f(n)=Theta(n^p). The common extended Case 2 with k=0 gives T(n)=Theta(n^2 log n).
Now impose exact unit costs and T(1)=1:
T(2)=4T(1)+2^2=4+4=8T(4)=4T(2)+4^2=32+16=48T(8)=4T(4)+8^2=192+64=256
The equivalent substitution is T(8)=4(4(4T(1)+4)+16)+64=256.
Level | Nodes | Subproblem size | Work per node | Total level work |
|---|---|---|---|---|
0 | 1 | 8 | 64 | 64 |
1 | 4 | 4 | 16 | 64 |
2 | 16 | 2 | 4 | 64 |
3 | 64 | 1 | Base cost 1 | 64 |
Thus the exact total is 64+64+64+64=256. More generally, every non-leaf level costs Theta(n^2), and there are logarithmically many levels, producing Theta(n^2 log n). The exact value needs the stated base case and unit costs; the Theta result describes growth.

How do all three Master Theorem cases differ?
Use the common extended form carefully. Case 1 needs f(n)=O(n^(p-epsilon)) for some epsilon>0, giving Theta(n^p). Case 2 needs f(n)=Theta(n^p log^k n) for k>=0, giving Theta(n^p log^(k+1) n). Case 3 needs f(n)=Omega(n^(p+epsilon)) plus a f(n/b) <= c f(n) for some c<1, giving Theta(f(n)).
Hold b=2, f(n)=n^2, T(1)=1 and n=8 fixed:
Recurrence |
| Case | Level totals | Exact total | Growth |
|---|---|---|---|---|---|
| 3 | 1 |
| 960 |
|
| 2 | 2 |
| 256 |
|
| 1 | 3 |
| 120 |
|
For Case 3, 2(n/2)^2=n^2/2, so regularity holds with c=1/2. Leaves dominate the first recurrence, all levels tie in the second, and the root dominates the third.

How do you derive the recurrence from code before applying the theorem?
Read the recursive calls and local work separately:
solve(n):
if n == 1: return 1
total = 0
repeat 4 times:
total = total + solve(n/2)
for i = 1 to n:
for j = 1 to n:
total = total + 1
return totalThe four calls give a=4. Every call receives n/2, so b=2. The nested n x n loops give f(n)=Theta(n^2). This is the section 2 recurrence, hence Theta(n^2 log n). Four sequential calls do not make the subproblem n/4, and a half-sized argument does not make a=2.
Space is a separate follow-up. With sequential evaluation and O(1) local state per active call, the maximum depth is log_2 n, so auxiliary stack space is O(log n). DSA using Java is an optional route for practising recursion, algorithms and complexity explanations.
What happens at the logarithmic boundary?
For T(n)=2T(n/2)+n log_2 n, we have a=2, b=2, p=1 and f(n)=Theta(n^p log^1 n). The extended Case 2 gives Theta(n log^2 n). A narrower textbook statement may cover only k=0, so state which theorem version you are using.
Now consider T(n)=2T(n/2)+n/log_2 n, with a constant base case for small n. It does not fit the stated k>=0 Case 2. At level i, total non-recursive work is n/(log_2 n-i). Across non-leaf levels, this sums to n(1+1/2+...+1/log_2 n)=Theta(n log log n), not Theta(n log n). The Master Theorem for GATE boundary guide gives a longer case-and-boundary treatment.
When does the Master Theorem not apply?
Take T(n)=T(n-1)+n, with T(1)=1. The recursive size is n-1, not n/b for constant b>1, so the theorem does not apply. Expansion gives T(5)=T(4)+5=T(3)+4+5=T(2)+3+4+5=T(1)+2+3+4+5=15, and the general sum is Theta(n^2).
For T(n)=T(n/3)+T(2n/3)+n, the subproblems have unequal sizes, so no single aT(n/b) term exists. At n=9, the first split has sizes 3 and 6, whose non-recursive work totals 3+6=9, equal to the root's work. Akra-Bazzi solves (1/3)^p+(2/3)^p=1, giving p=1 and Theta(n log n).
A concise model answer names the violated assumption, selects substitution, a recursion tree or Akra-Bazzi, and continues. "Master Theorem does not apply" is a diagnosis, not the end.
Which follow-ups expose a memorised Master Theorem answer?
Use five rapid responses:
Why
log_b(a)? At depthlog_b n, the leaf count isa^(log_b n)=n^(log_b a).Does the log base change Big-Theta? No. A constant base change contributes only a constant multiplier.
Can the theorem give the exact value 256? No. That value also needs
T(1)=1,n=8and exact unit costs.Why check regularity in Case 3? It stops irregular non-recursive work from re-expanding enough to defeat root dominance.
What if
nis not a power ofb? State floor or ceiling conventions and the needed regularity assumptions before arguing the same asymptotic class.
For more practice, use the broader DSA interview-question patterns and the Placement Preparation category to widen the drill without pretending every interview asks the same question.
Master Theorem interview answer: the 45-second version and next step
Normalise T(n)=aT(n/b)+f(n). Identify a, b and f, compute p=log_b a, compare valid polynomial or logarithmic gaps, check regularity where required, then state the Theta bound and the dominating level. In the core example, a=4, b=2, p=2, equal level costs give Theta(n^2 log n), and T(8)=256 under the stated costs.
Rehearse that example, the n-1 non-example and the unequal split aloud without notes. The Interview & Resume Preparation Course is an optional next step for structured interview rehearsal.
Keep learning
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.
Master Theorem MCQs: 12 Solved Questions with Explanations
Solve 12 Master Theorem MCQs with clear case selection, recursion-tree checks, gap cases, floors, substitutions, and recurrence ranking.
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.
Recursion Tree Method Interview Questions: Worked Traces and Model Answers
Learn how to turn a recurrence into a recursion tree, total each level, include the leaves and state a tight bound. Worked examples cover exact traces, dominant regions, code analysis and interview follow-ups.





