Divide and Conquer

Divide and conquer: split the problem into independent subproblems, solve each, combine the answers. Three steps, and the middle word is the one that matters.

The shape

1. Divide — break the input into smaller pieces.
2. Conquer — solve each piece, usually by recursing.
3. Combine — assemble the results.

You have already met three of these: merge sort (split in half, sort each, merge), quick sort (partition, sort each side) and binary search (throw away half, recurse on the rest).

⚠️ Independent is the whole distinction

Divide and conquer and dynamic programming have the same recursive shape, and people mix them up constantly. The difference is one property:

Merge sort's two halves share no element, so there is nothing a cache could hit. Fibonacci's two branches overlap enormously — fib(n-1) and fib(n-2) both need fib(n-3) — which is why it needs memoising and merge sort does not.

So the test is not "does it recurse twice". It is "do the recursive calls ever ask the same question".

The shape, minimally

    /** Maximum of an array, split down the middle. A loop is better - this shows the shape. */
    public static int max(int[] a, int low, int high) {
        if (low == high) {
            return a[low];                 // base case: one element
        }
        int mid = low + (high - low) / 2;
        return Math.max(max(a, low, mid), max(a, mid + 1, high));
    }

Honest about itself: this is O(n) with O(log n) stack, where the obvious loop is O(n) with no stack. Divide and conquer is not automatically a win — here it is just a clear illustration.

Where it genuinely wins

    public static long power(long base, int exponent) {
        if (exponent < 0) {
            throw new IllegalArgumentException("negative exponent");
        }
        if (exponent == 0) {
            return 1;
        }
        long half = power(base, exponent / 2);
        // Computed ONCE and squared. Writing power(b, e/2) * power(b, e/2) is the same value
        // and O(n) again, because the compiler will not share those two calls for you.
        return exponent % 2 == 0 ? half * half : half * half * base;
    }

x²⁰ is (x¹⁰)², so each step halves the exponent rather than decrementing it: O(log n) against the loop's O(n). For x⁶⁴ that is 6 multiplications instead of 64.

The comment marks the trap. Writing power(b, e/2) * power(b, e/2) is mathematically identical and computationally disastrous — it makes two full recursive calls instead of one, and the complexity collapses back to O(n). Nothing warns you; the answer is right and the speed is gone.

Getting something for free in the combine step

The best divide-and-conquer results come from noticing that the combine step already has information you want. Counting inversions — pairs of elements that are out of order, a measure of how unsorted a list is — is the classic example.

Brute force compares every pair: O(n²). But a merge sort already walks both halves in order, so the count comes almost free:

            } else if (buffer[right] < buffer[left]) {
                // Every remaining element in the left half is greater than this one,
                // so this single comparison accounts for all of them at once.
                count += mid - left + 1;
                a[i] = buffer[right++];

When an element from the right half is emitted early, it was smaller than everything still pending in the left half — so one comparison counts mid - left + 1 inversions at a stroke. Total cost: O(n log n), the same as the sort it rides along with.

A clever result like that deserves suspicion, so the test checks it against the definition:

        // Cross-check against the O(n^2) definition, which is what makes the clever
        // version trustworthy rather than merely plausible.
        int[] sample = {5, 2, 9, 1, 7, 3, 8, 4};
        long brute = 0;
        for (int i = 0; i < sample.length; i++) {
            for (int j = i + 1; j < sample.length; j++) {
                if (sample[i] > sample[j]) {
                    brute++;
                }
            }
        }
        Check.eq(countInversions(sample), brute, "agrees with the brute-force count");

That pattern — implement the slow obvious version and assert the fast one agrees — is the most useful testing habit in this whole track.

Working out the complexity

Most divide-and-conquer recurrences look like T(n) = a·T(n/b) + f(n): a subproblems of size n/b, plus f(n) to split and combine. Three common cases cover nearly everything you will meet:

The last row is not divide and conquer at all — the subproblems are not independent and they barely shrink. It is in the table because that recurrence is exactly what a problem looks like when you should be using dynamic programming instead.

What to remember

• Divide, conquer, combine — and the subproblems must be independent.
• Overlapping subproblems means you want DP, not this.
• Compute a shared recursive result once; calling it twice silently loses the speedup.
• Look for work the combine step can do for free.
• Cross-check a clever algorithm against the slow obvious one.