Algorithm Design Paradigms

Divide & Conquer

Split a problem into independent subproblems of the same shape, solve each recursively, then combine the results. The recursion tree — not the code — is where the runtime comes from (Recursion And Recurrences).

Three steps: divide (split the input), conquer (recurse on each piece), combine (merge the sub-results)
Correctness comes from induction: if the recursive calls solve their smaller inputs correctly, and combine is correct, the whole is correct
The classic win is turning an O(n²) combine-everything approach into O(n log n) by keeping subproblems independent
Mergesort, quicksort, binary search, and the Master Theorem's canonical form T(n) = aT(n/b) + f(n) are all divide-and-conquer
Not free: it only pays off when subproblems are truly independent — overlapping subproblems belong to Dynamic Programming instead

The template is almost always the same shape: a base case for trivially small input, a split into (usually two) smaller instances, a recursive call on each, and a combine step that assembles the final answer from the sub-answers. Mergesort is the textbook example — split the array in half, sort each half, merge the two sorted halves in linear time. The combine step's cost, multiplied across the recursion tree, is what the Master Theorem is solving for.

Closest pair of points — the shape of every D&C algorithm

static double closestPair(Point[] pts, int lo, int hi) {
    if (hi - lo <= 3) return bruteForce(pts, lo, hi);      // base case

    int mid = (lo + hi) / 2;
    double midX = pts[mid].x;

    double dLeft  = closestPair(pts, lo, mid);             // conquer left
    double dRight = closestPair(pts, mid, hi);             // conquer right
    double d = Math.min(dLeft, dRight);

    return combineAcrossStrip(pts, lo, hi, midX, d);       // combine: only check
}                                                           // points within d of the midline

The combine step is the hard part — it must do less than O(n) work per level, or the whole algorithm degrades to O(n²)

Recurrence shape → total runtime (Master Theorem intuition)
Recurrence	Combine cost	Total	Example
T(n) = 2T(n/2) + O(1)	constant	O(n)	binary tree traversal
T(n) = 2T(n/2) + O(n)	linear merge	O(n log n)	Mergesort
T(n) = 2T(n/2) + O(n²)	expensive combine	O(n²)	combine dominates — D&C bought nothing
T(n) = T(n/2) + O(1)	discard half, no merge	O(log n)	Binary Search And Variants