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
  1. — the total work at the leaves.
  2. — 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
  1. Is the recurrence even of this form? It needs the input shrinking by a factor, not an amount.
  2. Compute .
  3. Compare with → Case 1, 2 or 3.
  4. For Case 3 only, check regularity.
  5. 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Recursion