Divide and Conquer — Strategy, Patterns and Recurrences

Divide and conquer is the algorithmic pattern behind merge sort, binary search, fast Fourier transform, Strassen's matrix multiplication, and closest pair of points. If you understand D&C deeply, you understand why all of these algorithms work and how to design new ones.

The pattern is deceptively simple: split the problem, solve each half, combine. The complexity depends almost entirely on the combine step — and the Master Theorem gives you an algebraic shortcut to avoid solving the recurrence from scratch each time. Learning the Master Theorem once saves you dozens of recurrence derivations throughout your career.

The Three-Step Pattern

Every divide and conquer algorithm follows the same template:

1. Divide: Split the problem into subproblems (usually of equal or near-equal size)
2. Conquer: Solve each subproblem recursively (base case when small enough)
3. Combine: Merge subproblem solutions into the overall solution

The efficiency depends critically on the combine step. Merge sort's O(n log n) comes from an O(n) combine. Binary search has O(1) combine (no merging needed).

def divide_and_conquer(problem):
    # Base case
    if is_small_enough(problem):
        return solve_directly(problem)
    # Divide
    subproblems = divide(problem)
    # Conquer
    solutions = [divide_and_conquer(sub) for sub in subproblems]
    # Combine
    return combine(solutions)

The Master Theorem

For recurrences of the form T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1:

• Case 1: f(n) = O(n^(log_b(a) - ε)) → T(n) = Θ(n^log_b(a))
• Case 2: f(n) = Θ(n^log_b(a)) → T(n) = Θ(n^log_b(a) · log n)
• Case 3: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = Θ(f(n))

Examples: - Merge sort: T(n) = 2T(n/2) + O(n) → Case 2 → O(n log n) - Binary search: T(n) = T(n/2) + O(1) → Case 2 → O(log n) - Strassen: T(n) = 7T(n/2) + O(n²) → Case 1 → O(n^2.807) - Simple recursion: T(n) = 2T(n/2) + O(1) → Case 1 → O(n)

Canonical Examples

# Binary Search — O(log n)
def binary_search(arr, target, lo, hi):
    if lo > hi: return -1
    mid = (lo + hi) // 2
    if arr[mid] == target: return mid
    if arr[mid] < target: return binary_search(arr, target, mid+1, hi)
    return binary_search(arr, target, lo, mid-1)

# Merge Sort — O(n log n)
def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]: result.append(left[i]); i += 1
        else:                   result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

# Power function — O(log n)
def fast_power(base, exp):
    if exp == 0: return 1
    if exp % 2 == 0:
        half = fast_power(base, exp // 2)
        return half * half
    return base * fast_power(base, exp - 1)

print(fast_power(2, 10))  # 1024

When Divide and Conquer Pays Off

D&C pays off when: 1. Subproblems are independent (no shared state to communicate) 2. Subproblems are of equal or balanced size (imbalanced splits degrade to O(n²)) 3. The combine step is efficient (O(n) or less)

D&C does NOT pay off when: - Subproblems overlap heavily (use dynamic programming instead) - The combine step is expensive (e.g., O(n²) combine → O(n² log n) total, worse than naive)

Frequently Asked Questions