Divide and Conquer

Divide into smaller subproblems, solve recursively, combine results.

Pattern

Divide into smaller subproblems, solve recursively, combine results.

Algorithms

Binary search, merge sort, quicksort, quickselect, closest pair of points, divide-and-conquer multiplication, inversion counting, and divide-and-conquer DP optimization where prerequisites apply.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

#include <bits/stdc++.h>
using namespace std;

// inversions = pairs i < j with a[i] > a[j], counted while merge sorting
long long sortCount(vector<int>& a, vector<int>& tmp, int l, int r) {
    if (r - l < 2) return 0;
    int m = l + (r - l) / 2;
    long long inv = sortCount(a, tmp, l, m) + sortCount(a, tmp, m, r);
    int i = l, j = m, k = l;
    while (i < m && j < r) {
        if (a[j] < a[i]) { inv += m - i; tmp[k++] = a[j++]; }      // a[j] is smaller than all remaining left elements
        else tmp[k++] = a[i++];
    }
    while (i < m) tmp[k++] = a[i++];
    while (j < r) tmp[k++] = a[j++];
    copy(tmp.begin() + l, tmp.begin() + r, a.begin() + l);
    return inv;
}

// closest pair of points, O(n log n)
using P = pair<double, double>;
double dist(const P& a, const P& b) { return hypot(a.first - b.first, a.second - b.second); }
double closest(vector<P>& pts, int l, int r) {                    // pts[l, r) sorted by x; leaves them sorted by y
    if (r - l <= 3) {
        double best = 1e18;
        for (int i = l; i < r; ++i) for (int j = i + 1; j < r; ++j) best = min(best, dist(pts[i], pts[j]));
        sort(pts.begin() + l, pts.begin() + r, [](const P& a, const P& b) {
…

inversions of {8,4,2,1}: 6
inversion counts match O(n^2) brute force on 500 random arrays
closest pair among 2000 points: 0.587001 (brute force 0.587001)
Karatsuba on 64-digit polynomials equals schoolbook: true, base multiplications 972 vs 4096

Analysis

Recurrence setup, recursion-tree visualization, combine cost, and Master Theorem applicability. Compare divide-and-conquer with dynamic programming when subproblems overlap.

T(n) = T(n/2) + O(1) Merge sort, inversion count, closest pair T(n) = 2T(n/2) + O(n) T(n) = 3T(n/2) + O(n) O(n^log₂3) ≈ O(n^1.585) Quickselect (expected) T(n) ≈ T(n/2) + O(n)

For 64-digit inputs Karatsuba used 3⁵·4 = 972 base multiplications in the run, against 4096 for the schoolbook method. When subproblems overlap (naive Fibonacci recomputes the same values), divide and conquer wastes work — that is the signal to switch to dynamic programming.

Quiz

? During merging, a[j] from the right half is taken while `m − i` left elements remain. How many inversions does it add?
+ m − i :: Every remaining left element is larger than a[j] and comes before it.
- 1 :: It forms an inversion with each remaining left element.
- j − m :: Unrelated.
- 0 :: Taking from the right means inversions exist.

? Karatsuba's recurrence T(n) = 3T(n/2) + O(n) solves to…
+ Θ(n^log₂3) ≈ n^1.585 :: Master Theorem case 1.
- Θ(n log n) :: That needs a = 2.
- Θ(n²) :: The schoolbook bound.
- Θ(n) :: No.

? When does divide and conquer become wasteful?
+ When subproblems overlap and are solved repeatedly :: Use memoisation or DP.
- When subproblems are independent :: That is its ideal case.
- When n is a power of two :: Irrelevant.
- When the combine step is linear :: That is common and fine.