Micro-questions over the divide and conquer module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. The design question

1. Everyone can state “divide, conquer, combine”. What makes it a technique rather than a slogan?

Answer

You chose , and in . The design question is not “should I use divide and conquer?” but “what values of , and can I get away with?”

2. What does reducing buy?

Answer

It changes the exponent . Karatsuba: 4 → 3 multiplications, .

3. What does reducing buy?

Answer

A log factor, or nothing. Merge sort’s merge is what the costs.

4. State the single most useful design insight.

Answer

Reducing is worth far more than reducing . Strassen and Karatsuba are famous because they cut ; nobody is famous for a faster merge.


B. The vocabulary

5. Define the divide, conquer and combine steps.

Answer

Divide: how the input is split — usually trivial, its cost part of . Conquer: the recursive calls on inputs of size . Combine: the work turning sub-answers into the whole answer.

6. Which step matters most?

Answer

The combine — it is where almost all divide-and-conquer algorithms do their real work, and where the interesting ones do something clever.

7. What does “independent subproblems” mean, and what does it distinguish?

Answer

No subproblem’s answer is needed for another’s, and no two solve the same instance. Independence is what distinguishes divide and conquer from dynamic programming — when subproblems overlap, you memoise instead.

8. Why does a balanced split matter?

Answer

Balanced splits give depth; unbalanced ones degrade to depth — exactly quicksort’s worst case.

9. What is a base-case threshold, and what is a typical value?

Answer

The size below which you stop recursing and use a simple method. Real merge sorts switch to insertion sort at around 10–30 elements, because recursion’s constant factors dominate below that.


C. The catalogue

10. Compare tree traversal with merge sort.

Answer

Identical and . Only difference: combine versus combine — and that is the entire difference between and .

11. Why can merge sort never be made linear?

Answer

Any correct merge must look at every element, so the combine is irreducible, and it is paid once per level across levels.

12. What do binary search and fast power have in common?

Answer

Only one recursive call, so no branching — the tree is a path and the result is simply the depth. Any algorithm that discards a constant fraction each step and recurses once is .


D. Counting inversions

13. What is an inversion, and what is it used for?

Answer

A pair with and — a pair out of order. It measures how unsorted a list is, and is used in rank correlation statistics and collaborative filtering.

14. What is the brute force cost?

Answer

— check every pair.

15. State the merge insight.

Answer

When you take an element from the right half because it is smaller, the left half is sorted — so that element is smaller than every remaining element of the left half, all len(left) - i of them. That is len(left) - i inversions counted in one operation.

16. Write the line.

Answer
inv += len(left) - i

17. State the general design lesson.

Answer

The combine step you already needed for another reason turns out to compute the thing you wanted.


E. When it is the wrong tool

18. Max subarray has a clean divide-and-conquer solution. Is it a good algorithm for the problem?

Answer

No — the problem is solvable in by Kadane’s, so the D&C solution is a factor worse while being considerably longer. Measured: ~20× slower at , and the ratio grows.

19. What exactly does the D&C solution throw away?

Answer

The best subarray ending at position is computable from the one ending at . Divide and conquer splits because it does not know anything else about the problem.

20. State the lesson.

Answer

Being applicable is not the same as being right. A technique that ignores structure loses to one that uses it.

21. Give the three conditions for reaching for it.

Answer
  1. The problem splits into independent subproblems of the same kind.
  2. Combining is cheaper than solving the whole directly.
  3. The split is balanced, or you can make it so.

22. Give the four conditions for not reaching for it.

Answer
  1. Subproblems overlap → dynamic programming.
  2. A single linear pass suffices.
  3. The combine costs as much as brute force — recursion overhead for nothing.
  4. The subproblems are not independent — the recursion is not well-formed.

F. Reducing

23. Write the obvious split for multiplying two -digit numbers.

Answer

Four multiplications: , , , .

24. What does that give, and what is the verdict?

Answer

, , so — exactly the schoolbook method, with extra steps. Divide and conquer bought nothing.

25. State Karatsuba’s observation.

Answer

You do not need and separately, only their sum — and

You already have and , so one extra multiplication yields the middle term.

26. What is the resulting recurrence and complexity?

Answer

.

27. Why do real bignum libraries only use Karatsuba above a few hundred digits?

Answer

Each level pays additions and shifts that schoolbook does not, so the wall-clock crossover comes much later than the operation-count crossover.

28. State Strassen as the same move.

Answer

The obvious block decomposition needs 8 multiplications → → . Strassen found a way with 7 → .

29. State the shared insight in one sentence.

Answer

An extra addition is cheap; a multiplication is a whole recursive subproblem. Trading additions for multiplications changes the exponent, and nothing you do to the combine step will.


G. Traps

30. What is wrong with writing merge sort using arr[:mid]?

Answer

Slices copy, adding extra work per level and total memory. Pass indices instead.

31. How do you bound recursion depth at even with an unbalanced split?

Answer

Recurse on the smaller side and loop on the larger. The recursed side at most halves each time, so the depth is regardless.

32. Summarise divide and conquer in one sentence.

Answer

Split into independent pieces, recurse, and combine — where the design work is cutting the number of recursive calls, not speeding up the combine.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Algorithms