Section Recap

You've learned the divide and conquer approach: divide, conquer, combine.

Classic algorithms:

• Merge sort: $O(n \log n)$ sorting.
• Binary search: $O(\log n)$ lookup.
• QuickSelect: $O(n)$ expected selection.
• Karatsuba: $O(n^{1.585})$ multiplication.

Master Theorem: $T(n) = aT(n/b) + f(n)$ solves most D&C recurrences.

When to use D&C:

• Problem splits into independent subproblems.
• Subproblem structure matches original problem.
• Combination step is efficient.

D&C is a thinking framework. When you see a problem, ask: "Can I split this, solve pieces, and merge?" Many efficient algorithms follow this pattern.