Divide and Conquer: Core Concepts

Divide and conquer is a way of designing algorithms: split a problem into smaller instances of the same problem, solve those instances recursively, and build the answer for the original input from their answers. Merge sort, binary search, fast exponentiation, quickselect, Karatsuba multiplication and the FFT all follow this pattern. Once you recognize it, many problems that seem to need O(n^2) work turn out to be solvable in O(n log n) or better.

The three steps

1. Divide: split the input into subproblems, usually of roughly equal size. Two halves is the most common choice.
2. Conquer: solve each subproblem recursively. When a subproblem is small enough (the base case), solve it directly.
3. Combine: turn the subproblem answers into an answer for the whole input.

Different algorithms put the real work in different steps. In merge sort, dividing is trivial (cut at the middle) and combining, the merge of two sorted halves, does the heavy lifting. In quicksort and quickselect it is the other way around: partitioning around a pivot is the hard part and combining costs nothing.

def max_value(a, lo, hi):
    """Largest element of a[lo:hi] (non-empty), by divide and conquer."""
    if hi - lo == 1:                         # base case: one element
        return a[lo]
    mid = (lo + hi) // 2                     # divide
    left = max_value(a, lo, mid)             # conquer
    right = max_value(a, mid, hi)
    return left if left >= right else right  # combine

print(max_value([3, 9, 2, 7, 5], 0, 5))  # 9

This is no faster than a simple loop, but it shows the skeleton every divide-and-conquer algorithm shares: a base case, a split, recursive calls and a combine step.

Vocabulary

Decrease and conquer

Some algorithms discard all but one subproblem. Binary search compares the target with the middle element and continues in only one half, so the remaining range shrinks geometrically and the total work is O(log n).

def binary_search(a, target):
    lo, hi = 0, len(a)              # search in a[lo:hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1            # keep the right half
        else:
            hi = mid                # keep the left half
    return lo if lo < len(a) and a[lo] == target else -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3

When divide and conquer fits

It works well when the subproblems are independent and combining is cheaper than solving the whole problem from scratch. Good signs:

• The input splits naturally: halves of an array, high and low digits of a number, left and right sides of a plane.
• The answer for the whole is the answers for the parts plus some crossing information: pairs that straddle the split, or a subarray that passes through the middle.
• Subproblems do not share pieces, so each one is solved exactly once.

If subproblems overlap, plain recursion repeats work exponentially. The naive Fibonacci function is the classic warning sign: fib(n - 1) and fib(n - 2) both recompute fib(n - 3) and everything below it. That situation calls for dynamic programming (memoization or a table), not divide and conquer.

calls = 0

def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

fib(25)
print(calls)  # 242785 calls for one small answer: overlapping subproblems

Classic examples at a glance

Summary

• Divide and conquer means divide, conquer recursively, combine.
• The base case stops the recursion; the combine step usually decides the cost.
• Keeping only one subproblem (decrease and conquer) leads to logarithmic or linear algorithms.
• Independent subproblems suit divide and conquer; overlapping ones call for dynamic programming.