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

Updated 15 Nov 20265 min read
Master Theorem Interview Questions: Recurrence Traces and Model Answers

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=8

  • T(4)=4T(2)+4^2=32+16=48

  • T(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.

Recursion tree for T(n)=4T(n/2)+n^2 at n=8, with four equal-cost levels, 64 work per level, and a final total of 256.

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

p

Case

Level totals

Exact total

Growth

8T(n/2)+n^2

3

1

64, 128, 256, 512

960

Theta(n^3)

4T(n/2)+n^2

2

2

64, 64, 64, 64

256

Theta(n^2 log n)

2T(n/2)+n^2

1

3

64, 32, 16, 8

120

Theta(n^2)

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.

Three cost strips compare Master Theorem Cases 1, 2 and 3 for f(n)=n^2, with rising, equal and falling level totals and totals 960, 256 and 120.

How do you derive the recurrence from code before applying the theorem?

Read the recursive calls and local work separately:

Code
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 total

The 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:

  1. Why log_b(a)? At depth log_b n, the leaf count is a^(log_b n)=n^(log_b a).

  2. Does the log base change Big-Theta? No. A constant base change contributes only a constant multiplier.

  3. Can the theorem give the exact value 256? No. That value also needs T(1)=1, n=8 and exact unit costs.

  4. Why check regularity in Case 3? It stops irregular non-recursive work from re-expanding enough to defeat root dominance.

  5. What if n is not a power of b? 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.