What is the Master Theorem?
Learn the Master Theorem for divide-and-conquer recurrences, its three cases, and how to answer this DSA interview question.
Expected Interview Answer
The Master Theorem gives a direct formula for the time complexity of divide-and-conquer recurrences of the form T(n) = a·T(n/b) + f(n), by comparing f(n) against n^(log_b a) to determine whether the work is dominated by the recursive splits, the combine step, or is balanced between the two.
Here a is the number of subproblems, n/b is the size of each subproblem, and f(n) is the cost of dividing and combining outside the recursive calls. The theorem compares f(n) to n^(log_b a), called the critical exponent: if f(n) grows polynomially slower, the recursive splits dominate and T(n) = Θ(n^(log_b a)); if f(n) grows polynomially faster, the combine step dominates and T(n) = Θ(f(n)); if they grow at the same polynomial rate, both contribute and T(n) = Θ(n^(log_b a) · log n). Merge sort fits case 3 (a=2, b=2, f(n)=n, critical exponent 1, so Θ(n log n)); binary search fits case 2 conceptually (a=1, b=2, f(n)=O(1)); a naive recursive Fibonacci-like recurrence with a=2, b=1 falls outside the theorem’s applicability since b must be greater than 1. The theorem only applies to this specific recurrence shape — it doesn’t cover recurrences with subtractive terms like T(n-1), unequal subproblem sizes, or f(n) that isn’t polynomial-comparable to the critical exponent (those need the more general Akra-Bazzi method).
- Gives an O(1)-effort answer for common divide-and-conquer recurrences
- Directly explains merge sort’s Θ(n log n) and binary search’s Θ(log n)
- Clarifies which of split cost vs combine cost dominates total runtime
- Signals when a recurrence needs a more general tool like Akra-Bazzi instead
AI Mentor Explanation
A tournament splits into a subregions each running its own qualifier of size n/b, and after those a qualifiers report back, an f(n) amount of extra work is needed to combine the results into the next round’s bracket. If that combining work is small compared to how fast the qualifiers multiply, the qualifiers dominate the total effort; if the combining work is huge compared to the qualifier count, the combining dominates instead; and if they roughly match, both contribute equally with an extra logarithmic factor from the repeated rounds. This is exactly the tradeoff the Master Theorem quantifies: comparing the “number and size of subregions” against the “cost of merging brackets” to say which one drives total tournament-organizing effort. Just like a real tournament, the formula only applies cleanly when every subregion is the same size and count — an irregular bracket with subregions of wildly different sizes needs a different analysis entirely.
Step-by-Step Explanation
Step 1
Match the recurrence shape
Confirm the recurrence is T(n) = a·T(n/b) + f(n) with a ≥ 1, b > 1, and f(n) asymptotically positive.
Step 2
Compute the critical exponent
Calculate n^(log_b a), which represents the cost if only the recursive splits mattered.
Step 3
Compare f(n) to the critical exponent
Determine whether f(n) is polynomially smaller, polynomially larger, or of the same polynomial order.
Step 4
Apply the matching case
Case 1: Θ(n^(log_b a)); Case 2: Θ(n^(log_b a) log n); Case 3: Θ(f(n)) if the regularity condition also holds.
What Interviewer Expects
- State the recurrence form T(n) = a·T(n/b) + f(n) precisely, with the constraints a ≥ 1, b > 1
- Explain the critical exponent n^(log_b a) and what it represents
- Correctly classify a given recurrence (e.g. merge sort) into the right case
- Know the theorem’s limits: it does not apply to subtractive recurrences or unequal subproblem sizes
Common Mistakes
- Applying the theorem to recurrences like T(n) = T(n-1) + O(1), which is not the T(n/b) form it requires
- Forgetting the regularity condition needed for case 3 (a·f(n/b) ≤ c·f(n) for some c < 1)
- Miscomputing the critical exponent log_b a, e.g. mixing up a and b
- Assuming the theorem covers every divide-and-conquer recurrence rather than just this specific polynomial-comparable shape
Best Answer (HR Friendly)
“The Master Theorem is a shortcut formula for figuring out the time complexity of a lot of divide-and-conquer algorithms without solving the recurrence from scratch. I compare how much work happens outside the recursive calls to how fast the number of subproblems grows, and that comparison tells me directly whether the algorithm’s runtime is dominated by the splitting, the combining, or both — which is exactly how I’d explain why merge sort ends up being Θ(n log n).”
Code Example
import math
def master_theorem_case(a, b, f_exponent):
"""
Classifies T(n) = a*T(n/b) + f(n) where f(n) = Theta(n^f_exponent).
Returns which case applies (1, 2, or 3) plus the resulting Theta bound.
"""
critical_exponent = math.log(a, b)
if f_exponent < critical_exponent:
return f"Case 1: Theta(n^{critical_exponent:.3f})"
elif math.isclose(f_exponent, critical_exponent):
return f"Case 2: Theta(n^{critical_exponent:.3f} * log n)"
else:
return f"Case 3: Theta(n^{f_exponent}) # requires regularity condition"
# Merge sort: T(n) = 2T(n/2) + O(n)
print(master_theorem_case(a=2, b=2, f_exponent=1)) # Case 2: Theta(n * log n)Follow-up Questions
- How would you classify the recurrence for Strassen’s matrix multiplication, T(n) = 7T(n/2) + O(n²)?
- What is the regularity condition required for case 3, and why is it needed?
- How does the Akra-Bazzi method generalize beyond what the Master Theorem can handle?
- Why does the recurrence T(n) = T(n-1) + O(n) fall outside the Master Theorem’s scope?
MCQ Practice
1. What is the recurrence form the Master Theorem applies to?
The Master Theorem specifically applies to recurrences of the form T(n) = a·T(n/b) + f(n) with a ≥ 1 and b > 1.
2. Merge sort’s recurrence is T(n) = 2T(n/2) + O(n). Which Master Theorem case applies?
Here the critical exponent log_2 2 = 1 equals f(n)'s growth rate n^1, which is case 2, giving Theta(n log n).
3. Which recurrence is NOT directly solvable by the Master Theorem?
T(n) = T(n-1) + n is a subtractive recurrence, not the T(n/b) divide-and-conquer form the Master Theorem requires.
Flash Cards
What recurrence form does the Master Theorem solve? — T(n) = a·T(n/b) + f(n), where a ≥ 1 and b > 1.
What is the “critical exponent” in the Master Theorem? — n^(log_b a), the growth rate if only the recursive splitting mattered.
Which case gives merge sort its Theta(n log n) bound? — Case 2, since f(n) = n matches the critical exponent n^(log_2 2) = n.
What recurrence shape is outside the Master Theorem’s scope? — Subtractive recurrences like T(n) = T(n-1) + f(n), or recurrences with unequal subproblem sizes.