## What is it? Divide and Conquer is an algorithm design paradigm that solves a problem by splitting it into smaller sub-problems, solving each recursively, and combining the results. Merge Sort and Quick Sort are classic examples. ## How it works Three steps applied recursively: 1. **Divide** — split the problem into 2 (or more) smaller sub-problems of the same type 2. **Conquer** — solve each sub-problem recursively; base case is solved directly 3. **Combine** — merge/aggregate the sub-problem solutions to form the solution for the original problem Example (Merge Sort): - Divide array in half, sort each half, merge two sorted halves ## When to use - Sorting (Merge Sort, Quick Sort) - Searching (Binary Search) - Matrix multiplication (Strassen) - Finding the closest pair of points - Problems that can be expressed as "solve on left half + solve on right half + combine" ## Key Points - Often leads to O(n log n) algorithms where brute force is O(n²) - Recurrence relation: T(n) = 2T(n/2) + O(n) → O(n log n) by Master Theorem - Overhead of recursion and combining must be accounted for