Micro-questions over the Master Theorem module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The idea
1. What two numbers does a divide-and-conquer recurrence’s answer depend on?
Answer
- — the total work at the leaves.
- — the work at the root.
2. State the whole theorem in one sentence.
Answer
Compare those two and whichever is bigger wins; if they tie, the answer is their common value times the number of levels.
3. Where is all the precision?
Answer
In what “bigger” has to mean.
B. The vocabulary
4. What is the critical exponent?
Answer
, sometimes the watershed exponent — the exponent at which leaf work and root work balance. Everything in the theorem is a comparison against .
5. What does “polynomially larger” mean?
Answer
Larger by a factor of for some fixed .
6. Is polynomially larger than ?
Answer
No. grows slower than for every positive , however small. This distinction is the single most important idea in the lesson.
7. What is the regularity condition, in symbols and in words?
Answer
for some and all large . In words: the total combine work must actually shrink as you go down the tree, by a constant factor.
8. Why does the regularity condition exist?
Answer
To exclude pathological functions that oscillate. It holds for every polynomial you will meet in practice.
9. What is “the gap”?
Answer
The region where the theorem says nothing — when is larger or smaller than but only by a logarithmic factor rather than a polynomial one.
C. The theorem
10. State Case 1 in symbols and in words.
Answer
for some .
The leaves are polynomially more work, so the leaves dominate.
11. State Case 2.
Answer
, .
The two match, so every level does about the same work — total is that times the number of levels.
12. State Case 3.
Answer
for some , and regularity holds .
The root is polynomially more work, so the root dominates.
13. What is the doing in Cases 1 and 3?
Answer
All the work. It is what makes “smaller” and “larger” mean polynomially so — exactly what versus fails to satisfy.
D. The decision procedure
14. Give the five steps in order.
Answer
- Is the recurrence even of this form? It needs the input shrinking by a factor, not an amount.
- Compute .
- Compare with → Case 1, 2 or 3.
- For Case 3 only, check regularity.
- If the comparison is “larger/smaller but only logarithmically”, you are in the gap — draw the tree.
15. Why does regularity hold automatically for ?
Answer
, and Case 3 already requires , which forces .
16. Solve merge sort.
Answer
. , so . They match, . Case 2: .
17. Solve binary search.
Answer
. , so . They match, . Case 2: .
18. Why does binary search surprise people?
Answer
It is Case 2, not Case 1. People expect the “one branch” recurrence to be special; with the critical exponent is 0, and constant work matches exactly.
19. Solve Strassen’s algorithm.
Answer
. . Is polynomially smaller? Yes, . Case 1: .
20. Why is Strassen famous?
Answer
Naive matrix multiplication is ; the same combine work with seven subproblems instead of eight drops the exponent to 2.807.
E. The trap
21. . Someone says ”, so Case 3, answer ”. Find both errors.
Answer
Error one: Case 3 needs for fixed . Here , and eventually falls behind for any . No valid exists.
Error two: the conclusion is also wrong — falling in the gap does not mean the answer is whatever Case 3 would have said.
22. Derive the true answer by tree.
Answer
Level : . Summing :
23. Can Case 2 handle it after all?
Answer
Yes — with , giving , the same answer. The trap is not that the recurrence is unsolvable; it is that reaching for Case 3 because ” looks bigger” gives the wrong answer.
F. Where it fails
24. Failure 1 — what, and why does it matter most in interviews?
Answer
Subtractive shrinking. has no at all. It matters because — naive Fibonacci — looks superficially like a divide-and-conquer recurrence and is nothing of the sort.
25. What is the tree answer for ?
Answer
Depth , work doubling per level → . Measured: 2,047 nodes at , 2,097,151 at .
26. Failure 3 — what is it, and what is the example?
Answer
Subproblems of different sizes. — quicksort with a guaranteed 1:2 split. The theorem assumes identical subproblems of size .
27. What does the tree give, and what is the useful takeaway?
Answer
Every level does work; the longest path has length , so . Even a lopsided constant-ratio split gives — quicksort does not need good pivots, only pivots that are not catastrophically bad.
28. What generalisation handles unequal splits?
Answer
The Akra–Bazzi method. Worth knowing the name; not worth memorising the formula.
G. Traps
29. Is it or , and what is the sanity check?
Answer
. For it is , not . Sanity check: more subproblems should give a larger exponent.
30. Does Case 2 always contribute exactly one ?
Answer
No. With the answer carries . For you get .
31. When does the theorem give only rather than ?
Answer
When your is itself only an upper bound — if you wrote for the combine step without knowing it is exactly linear, the conclusion is an upper bound too.
32. What does the theorem actually describe?
Answer
The recurrence, not the algorithm. Derive the recurrence wrongly — miscounting subproblems, or including recursive work in — and the theorem will faithfully give the right answer to the wrong question.
33. Summarise the theorem in one sentence.
Answer
Compare root work against leaf work ; whichever is polynomially bigger is the answer, and a tie costs one extra per level.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- The Master Theorem — the module
- Recursion Trees & Recurrences — Question Bank — where the three cases are derived
- Divide and Conquer — the design pattern it costs
Software engineering
Infrastructure & security
Computer science
Hardware & engineering