Divide-and-Conquer Reasoning

Split, Solve, Combine

Divide-and-conquer turns slow algorithms fast using a three-step pattern: divide a problem into smaller subproblems, conquer them recursively, and combine their answers.

Merge sort is the model example: split a list, sort each half, and merge them. Binary search is a degenerate form that discards one half.

Efficiency comes from shrinking problem size. The cost is captured by a recurrence like $T(n) = 2T(n/2) + O(n)$, meaning two half-size subproblems plus linear work, solving to $O(n \log n)$. The Master Theorem acts as a shortcut to solve these.

When It Works & Pitfalls

Divide-and-conquer succeeds when a problem decomposes into independent subproblems and their solutions combine cheaply, turning quadratic brute force into $O(n \log n)$.

Common pitfall: Applying divide-and-conquer when the combine step is expensive, or when subproblems overlap and repeat work exponentially.

If subproblems overlap, plain divide-and-conquer fails. That is the exact signal that dynamic programming, which stores and reuses subproblem answers, is the correct tool.