Divide & Conquer

Chapter 1: Maximum Subarray

You bought a stock on some day and sold it on a later day. Looking at the daily price changes (not prices, but changes: +3, -2, +5, -1, ...), the profit you made is the sum of the daily changes from your buy day to your sell day. The question: which contiguous window of days maximizes your total profit?

This is the maximum subarray problem: given an array A of n numbers (positive and negative), find the contiguous subarray A[i..j] whose elements have the largest sum. If all numbers are positive, the answer is the whole array. If all are negative, the answer is the single least-negative element. The interesting case is a mix of positives and negatives.

The brute-force approach checks all O(n²) pairs (i, j) and sums each subarray in O(n) time, giving O(n³). We can precompute prefix sums to bring it down to O(n²). But divide-and-conquer does it in O(n log n).

The D&C Strategy

Split the array at the midpoint. The maximum subarray must lie in exactly one of three places:

Cases 1 and 2 are recursive calls on halves. Case 3 is the combine step: we find the maximum subarray crossing the midpoint by scanning left from mid and right from mid+1, keeping running sums. This takes O(n) time.

The recurrence is T(n) = 2T(n/2) + Θ(n). This is the same recurrence as merge sort, so the solution is Θ(n log n).

Kadane's Algorithm: The O(n) Solution

There is a simpler and faster approach. Kadane's algorithm scans left to right, maintaining the maximum subarray ending at the current position. At each position, either extend the current subarray or start fresh.

python
def kadane(A):
    """Return (max_sum, start, end) of maximum subarray."""
    max_ending_here = 0
    max_so_far = float('-inf')
    start = end = temp_start = 0
    for j in range(len(A)):
        max_ending_here += A[j]
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            start = temp_start
            end = j
        if max_ending_here < 0:
            max_ending_here = 0
            temp_start = j + 1
    return max_so_far, start, end

# Example
A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(kadane(A))  # (6, 3, 6) → subarray [4, -1, 2, 1]

Kadane's is O(n) — strictly better than D&C's O(n log n). So why study the D&C version? Because the technique matters more than this specific problem. The same "left / right / crossing" decomposition appears in closest pair, count inversions, and many geometry problems where Kadane's trick does not apply.

Hand Trace: Step by Step

Let us trace the D&C algorithm on A = [-2, 1, -3, 4, -1, 2, 1, -5, 4] completely by hand. The array has 9 elements, so mid = 4.

The crossing subarray [4, -1, 2, 1] wins with sum 6. Notice how the crossing case found something neither recursive call could: a subarray spanning the midpoint. This is why the crossing check is essential — without it, we would have reported sum 4 instead of 6.

Complete D&C Implementation

python
def max_crossing_subarray(A, low, mid, high):
    """Find max subarray that crosses the midpoint. O(n)."""
    # Scan left from mid
    left_sum = float('-inf')
    total = 0
    max_left = mid
    for i in range(mid, low - 1, -1):
        total += A[i]
        if total > left_sum:
            left_sum = total
            max_left = i

    # Scan right from mid+1
    right_sum = float('-inf')
    total = 0
    max_right = mid + 1
    for j in range(mid + 1, high + 1):
        total += A[j]
        if total > right_sum:
            right_sum = total
            max_right = j

    return max_left, max_right, left_sum + right_sum

def max_subarray_dc(A, low, high):
    """Find max subarray in A[low..high] using D&C. O(n log n)."""
    if low == high:  # base case: single element
        return low, high, A[low]

    mid = (low + high) // 2

    # Recurse on left and right halves
    ll, lr, lsum = max_subarray_dc(A, low, mid)
    rl, rr, rsum = max_subarray_dc(A, mid + 1, high)
    cl, cr, csum = max_crossing_subarray(A, low, mid, high)

    # Return the best of three cases
    if lsum ≥ rsum and lsum ≥ csum:
        return ll, lr, lsum
    elif rsum ≥ lsum and rsum ≥ csum:
        return rl, rr, rsum
    else:
        return cl, cr, csum

# Test
A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
l, r, s = max_subarray_dc(A, 0, len(A) - 1)
print(f"Max subarray A[{l}..{r}] = {A[l:r+1]}, sum = {s}")
# Max subarray A[3..6] = [4, -1, 2, 1], sum = 6

Worked Example

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Midpoint index = 4 (value -1).

The crossing subarray wins with sum 6. This matches Kadane's output: [4, -1, 2, 1] at indices 3..6.

When All Elements Are Negative

A subtle edge case: what if every element is negative? The D&C algorithm handles this correctly because the base case returns single elements, and the max of all single-element returns is the least-negative element. Kadane's algorithm (as written above) also handles this, since we initialize max_so_far to negative infinity and track individual elements.

Some implementations of Kadane's reset max_ending_here to 0 when it goes negative. This variant returns 0 for all-negative arrays (the "empty subarray"). Whether the empty subarray is allowed depends on the problem statement — always clarify in an interview.

Complexity Comparison

The progression from O(n³) to O(n) illustrates a deep point about algorithm design. Each improvement comes from a different insight: prefix sums avoid redundant addition, D&C avoids redundant pair-checking, and Kadane's exploits the sequential structure. The D&C approach is not the fastest here, but the technique — splitting into left, right, and crossing — generalizes to problems (like closest pair) where Kadane's trick does not work.

Chapter 2: Strassen's Algorithm

Multiplying two n×n matrices the way you learned in linear algebra takes Θ(n³) time: each of the n² entries in the result is the dot product of a row and a column, and each dot product sums n terms. For n=1000, that is a billion multiplications. Can we do better?

In 1969, Volker Strassen shocked the mathematics community by showing that the answer is yes. He found a way to multiply 2×2 matrices using 7 multiplications instead of 8. That one saved multiplication, applied recursively, drops the running time from O(n³) to O(n^2.807). The improvement seems small for tiny matrices but is enormous at scale.

The Naive D&C Approach: Still O(n³)

Partition each n×n matrix into four (n/2)×(n/2) submatrices:

From the definition of matrix multiplication:

This requires 8 multiplications of (n/2)×(n/2) matrices and 4 additions. The recurrence is T(n) = 8T(n/2) + Θ(n²). Solving it (we will learn how later in this chapter), the answer is T(n) = Θ(n³) — no better than the schoolbook method. The problem: 8 recursive multiplications. Each halving creates 8 subproblems, so the work grows as 8^{log n} = n^log₂8 = n³.

Strassen's Trick: 7 Multiplications

Strassen defined 7 cleverly chosen products of sums and differences of submatrices:

Then the four quadrants of C are computed using only additions and subtractions of the P_i:

Worked Example: 2×2 Matrices

Let us verify Strassen with concrete numbers.

All four entries match. Seven multiplications, more additions, but the same result.

When to Use Strassen in Practice

In practice, the constant factor in Strassen is large (18 additions vs 4 for naive). Libraries like BLAS switch to Strassen only when n exceeds a crossover point (typically n ≥ 64-256). Below that, the cache-friendly naive algorithm with loop tiling wins.

Why 7 and Not Fewer?

Can we do better than 7? For 2×2 matrices, Hopcroft and Kerr (1971) proved that 7 is optimal — you cannot multiply 2×2 matrices with fewer than 7 multiplications. But for larger block sizes, you can sometimes do better. The current best algorithm for general matrix multiplication achieves exponent ω ≈ 2.371 (Alman-Williams 2024), though its constant factor is so enormous that it is never used in practice.

The practical state of the art is:

Implementation: Strassen in Python

python
import numpy as np

def strassen(A, B):
    """Multiply two square matrices using Strassen's algorithm."""
    n = A.shape[0]
    if n ≤ 64:  # crossover to naive for small matrices
        return A @ B

    mid = n // 2
    A11, A12 = A[:mid, :mid], A[:mid, mid:]
    A21, A22 = A[mid:, :mid], A[mid:, mid:]
    B11, B12 = B[:mid, :mid], B[:mid, mid:]
    B21, B22 = B[mid:, :mid], B[mid:, mid:]

    # 7 recursive multiplications
    P1 = strassen(A11, B12 - B22)
    P2 = strassen(A11 + A12, B22)
    P3 = strassen(A21 + A22, B11)
    P4 = strassen(A22, B21 - B11)
    P5 = strassen(A11 + A22, B11 + B22)
    P6 = strassen(A12 - A22, B21 + B22)
    P7 = strassen(A11 - A21, B11 + B12)

    # Combine with additions only
    C = np.zeros((n, n))
    C[:mid, :mid] = P5 + P4 - P2 + P6
    C[:mid, mid:] = P1 + P2
    C[mid:, :mid] = P3 + P4
    C[mid:, mid:] = P5 + P1 - P3 - P7
    return C

Notice the crossover at n=64. Below this threshold, we fall back to NumPy's built-in matrix multiplication (which uses optimized BLAS). This hybrid approach is how real implementations work — Strassen for the top levels of recursion, naive for the small base cases where cache performance matters more than asymptotic complexity.

Verifying Strassen's Formulas

The P_i formulas look magical. Let us verify C₁₁ = P₅ + P₄ - P₂ + P₆ algebraically to see that Strassen did not just get lucky.

Everything cancels except the two terms we need. Strassen found these particular linear combinations through careful algebraic manipulation. The same verification works for C₁₂, C₂₁, and C₂₂ — each P_i combination produces exactly the right pair of terms while canceling everything else.

Chapter 3: Recurrences

Every divide-and-conquer algorithm has a natural recurrence that describes its running time. You split a problem of size n into a subproblems of size n/b, do f(n) work to divide and combine, and solve each subproblem recursively. The result is:

Where:

• a = number of subproblems (≥ 1)
• n/b = size of each subproblem (b > 1)
• f(n) = cost of dividing and combining (the non-recursive work)

Let us see this for the algorithms we have studied:

There are three standard methods to solve recurrences:

The Substitution Method

The substitution method has two steps: (1) guess the form of the solution, and (2) prove the guess is correct using mathematical induction.

Example: prove that T(n) = 2T(n/2) + n is O(n log n).

The key trick: we needed cn - n ≥ 0, i.e., c ≥ 1. Choose c = 1 and the proof goes through. The base case T(1) = 1 ≤ c · 1 · log 1 = 0 fails, but we can handle small cases separately (T(2) = 4 ≤ 2 · 2 · 1 = 4 works).

Substitution Method: Common Tricks

Substitution Method: A Harder Example

Prove that T(n) = 2T(⌊n/2⌋) + 1 is O(n).

The trick: when the residual does not cooperate, subtract a lower-order term from your guess. This is the most common substitution technique and it comes up in interviews. The guess T(n) ≤ cn - d still implies T(n) = O(n), since cn - d ≤ cn.

Chapter 4: Recursion Trees

The substitution method requires a guess. But where does the guess come from? The recursion tree method gives you a visual way to derive it. Draw the tree of recursive calls, compute the work at each level, and sum the geometric series.

Building a Recursion Tree

For T(n) = 2T(n/2) + cn (merge sort), the tree looks like this:

Every level does exactly cn work. There are log₂(n) + 1 levels. Total: cn · (log₂(n) + 1) = Θ(n log n). This confirms our substitution proof from Chapter 3.

Example: T(n) = 3T(n/4) + cn²

The total work is a geometric series with ratio r = 3/16 < 1:

The ratio r = 3/16 < 1 means the series converges — the root level dominates. The total is Θ(n²), which is the same as f(n). This is Master Theorem Case 3 (the combine cost dominates).

Example: T(n) = T(n/3) + T(2n/3) + cn

This recurrence has unequal subproblems — the master theorem does not apply directly. But the recursion tree still works.

The shortest path from root to leaf is log₃(n) (always taking the n/3 branch). The longest is log_3/2(n) (always taking the 2n/3 branch). So the tree has between log₃(n) and log_3/2(n) full levels. Each full level costs cn. The total is Θ(n log n) — same as merge sort, even though the split is uneven.

Example: T(n) = 4T(n/2) + n (Case 1)

The series is n + 2n + 4n + ... + n² — a growing geometric series with ratio 2. The last term (leaves) dominates: n². Total = Θ(n²). This is Master Theorem Case 1: the recursion creates so many subproblems (4 subproblems at half size) that the leaf work swamps the combine work.

Notice the contrast with merge sort's tree (2 subproblems at half size, O(n) combine): every level costs the same. With 4 subproblems at half size, each level doubles the previous level's cost, so the leaves dominate.

Geometric Series Cheat Sheet

Recursion tree totals always reduce to geometric series. Here is the pattern you need:

Computing the Ratio r

For T(n) = aT(n/b) + f(n) where f(n) = cn^d, the ratio of consecutive levels is:

This single number tells you everything:

• r < 1 means a < b^d — fewer subproblems than the shrinkage compensates for. Case 3.
• r = 1 means a = b^d — perfect balance. Case 2.
• r > 1 means a > b^d — too many subproblems. Case 1.

For merge sort: a=2, b=2, d=1. r = 2/2¹ = 1. Case 2. For Strassen: a=7, b=2, d=2. r = 7/4 > 1. Case 1. For T(n)=3T(n/4)+n²: a=3, b=4, d=2. r = 3/16 < 1. Case 3.

How to Draw a Recursion Tree on a Whiteboard

In an interview, you will often need to draw a recursion tree to derive a bound. Here is a systematic approach:

Practice: Derive T(n) = 2T(n/2) + n²

Chapter 5: The Master Theorem

Drawing a recursion tree every time is tedious. The master theorem gives you the answer directly for any recurrence of the form T(n) = aT(n/b) + f(n), where a ≥ 1 and b > 1.

The key quantity is n^log_ba — this is the total number of leaves in the recursion tree. The theorem compares f(n) (work per level at the top) with n^log_ba (work at the bottom). Whichever is bigger wins.

How to Use It: Step by Step

Worked Examples

Example 1: T(n) = 9T(n/3) + n

Example 2: T(n) = T(2n/3) + 1

Example 3: T(n) = 3T(n/4) + n log n

Example 4: T(n) = 2T(n/2) + n log n

Intuition: Why Three Cases?

The recursion tree for T(n) = aT(n/b) + f(n) has log_b(n) levels. At level k, there are a^k nodes, each doing f(n/b^k) work. The total work at level k is a^k · f(n/b^k). The leaves (level log_b(n)) contribute Θ(n^log_ba) total work, since there are a^log_bn = n^log_ba of them.

Now imagine the work at each level as a bar in a bar chart:

Think of it as a tug-of-war between "recursion cost" (driven by a and b) and "combine cost" (f(n)). The master theorem tells you who wins.

Extended Master Theorem (Akra-Bazzi)

The master theorem only handles recurrences with equal-size subproblems. What about T(n) = T(n/3) + T(2n/3) + n? The Akra-Bazzi method handles these generalized recurrences of the form:

Find p such that ∑ a_ib_i^p = 1. Then T(n) = Θ(n^p(1 + ∫₁ⁿ f(x)/x^p+1 dx)). For T(n) = T(n/3) + T(2n/3) + n: find p such that (1/3)^p + (2/3)^p = 1. By inspection, p = 1 works: 1/3 + 2/3 = 1. The integral gives a log n factor. So T(n) = Θ(n log n), confirming our recursion tree analysis.

You do not need to memorize Akra-Bazzi for interviews, but knowing it exists shows depth. When the master theorem fails (unequal splits, non-polynomial f(n)), Akra-Bazzi is the fallback.

The Regularity Condition (Case 3)

Case 3 has an extra condition: af(n/b) ≤ cf(n) for some c < 1 and all sufficiently large n. This is the regularity condition. It ensures that f(n) does not have pathological behavior (like oscillating). For all "normal" functions (polynomials, n log n, etc.), the regularity condition is satisfied automatically. You only need to worry about it for exotic functions.

To verify it: plug in and check that the inequality holds. For f(n) = n² with a=3, b=4: 3(n/4)² = 3n²/16 ≤ cn² requires c ≥ 3/16. Since 3/16 < 1, the condition is satisfied with c = 3/16.

Master Theorem Quick Reference

Chapter 6: D&C Showcase

This is the payoff chapter. Below is a single simulation that visualizes four divide-and-conquer algorithms side by side. Select an algorithm, set the input size, and watch the recursive decomposition happen step by step. Each algorithm follows the same three-step pattern — divide, conquer, combine — but the specific strategy differs.

Each algorithm demonstrates a different aspect of divide-and-conquer:

D&C Design Spectrum

Every D&C algorithm sits somewhere on a spectrum between "easy divide, hard combine" and "hard divide, easy combine". Understanding where each algorithm sits helps you design new ones.

The Closest Pair Algorithm in Detail

Closest pair is the most elegant D&C algorithm beyond sorting. Let us trace through the key ideas:

The recurrence is T(n) = 2T(n/2) + O(n log n) — not O(n) — because we sort the strip by y at each level. This gives T(n) = O(n log² n). However, with a clever pre-sorting trick (maintain a separate y-sorted list alongside the x-sorted list), we can reduce the combine step to O(n), giving the optimal T(n) = O(n log n).

Stability and In-Place Considerations

Two practical properties distinguish D&C sorting algorithms in interviews:

Stability. A sorting algorithm is stable if equal elements maintain their relative order. Merge sort is stable (we take from the left array when equal). Quicksort is not stable in its standard implementation. This matters when sorting database records by a secondary key.

In-place. Merge sort requires O(n) extra space for the merge step. Quicksort partitions in-place using O(log n) stack space. When memory is tight, quicksort wins despite its O(n²) worst case (mitigated by random pivot selection).

Merge Sort: Split Trivially, Merge Carefully

python
def merge_sort(A):
    if len(A) ≤ 1:
        return A
    mid = len(A) // 2
    left = merge_sort(A[:mid])      # Conquer left half
    right = merge_sort(A[mid:])     # Conquer right half
    return merge(left, right)       # Combine: O(n) merge

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

Quicksort: Partition Carefully, Combine Trivially

python
def quicksort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)  # Divide: all hard work here
        quicksort(A, lo, p - 1)   # Conquer left
        quicksort(A, p + 1, hi)   # Conquer right
        # Combine: nothing — array is sorted in place!

def partition(A, lo, hi):
    pivot = A[hi]
    i = lo - 1
    for j in range(lo, hi):
        if A[j] ≤ pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[hi] = A[hi], A[i + 1]
    return i + 1

Chapter 7: More D&C Algorithms

Closest Pair of Points: O(n log n)

Given n points in the plane, find the pair with the smallest Euclidean distance. The brute-force approach checks all O(n²) pairs. D&C brings it down to O(n log n).

The "at most 7 comparisons" is the non-obvious part, and it is the key insight that makes the algorithm O(n log n) instead of O(n²). Let us prove it carefully.

Why the Strip Check is O(n)

Consider the strip: all points within distance δ of the dividing line. We sort these points by y-coordinate. For each point p, we need to check if any subsequent point (in y-order) is closer than δ.

How many subsequent points can possibly be within distance δ? Imagine a δ×2δ rectangle centered on the dividing line, with p at the bottom. This rectangle extends δ to the left and δ to the right of the midline, and δ upward from p.

Divide this rectangle into 8 cells of size (δ/2)×(δ/2). Each cell has diagonal δ/√2 < δ. So each cell can contain at most one point (if it contained two, they would be closer than δ, contradicting the fact that δ is the minimum distance within each half). Therefore, the rectangle contains at most 8 points, and since p is one of them, there are at most 7 others to check.

This argument is subtle and frequently tested in interviews. The interviewer wants to hear: (1) sort strip by y, (2) for each point check only next 7, (3) the "8 points in a rectangle" packing argument.

python
import math

def closest_pair(points):
    """Return (dist, p1, p2) for closest pair."""
    pts = sorted(points, key=lambda p: p[0])
    return _cp(pts)

def _cp(pts):
    n = len(pts)
    if n ≤ 3:
        return brute_force(pts)
    mid = n // 2
    dl, pl1, pl2 = _cp(pts[:mid])
    dr, pr1, pr2 = _cp(pts[mid:])
    if dl < dr:
        delta, best = dl, (dl, pl1, pl2)
    else:
        delta, best = dr, (dr, pr1, pr2)
    # Check strip
    mid_x = pts[mid][0]
    strip = [p for p in pts if abs(p[0] - mid_x) < delta]
    strip.sort(key=lambda p: p[1])
    for i in range(len(strip)):
        j = i + 1
        while j < len(strip) and strip[j][1] - strip[i][1] < delta:
            d = math.dist(strip[i], strip[j])
            if d < best[0]:
                best = (d, strip[i], strip[j])
            j += 1
    return best

Karatsuba Integer Multiplication: O(n^1.585)

Multiplying two n-digit numbers the grade-school way takes O(n²) single-digit multiplications. Karatsuba (1960) showed how to do it in O(n^log₂3) ≈ O(n^1.585) using the same D&C trick as Strassen: reduce 4 multiplications to 3.

Split each n-digit number into two halves:

python
def karatsuba(x, y):
    """Multiply two non-negative integers using Karatsuba."""
    if x < 10 or y < 10:
        return x * y
    n = max(len(str(x)), len(str(y)))
    m = n // 2
    p = 10 ** m
    x1, x0 = divmod(x, p)
    y1, y0 = divmod(y, p)
    z2 = karatsuba(x1, y1)
    z0 = karatsuba(x0, y0)
    z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0
    return z2 * p * p + z1 * p + z0

print(karatsuba(1234, 5678))  # 7006652

Karatsuba: Worked Example

Let us multiply 1234 × 5678 step by step:

Grade-school multiplication of 1234 × 5678 needs 4 × 4 = 16 digit-multiplications. Karatsuba used 3 half-size multiplications (each of 2-digit numbers). For 2-digit numbers the savings are modest, but for 1024-digit RSA keys, Karatsuba saves 25% at each recursion level, compounding to a 40% speedup overall.

Binary Search as D&C

Binary search is the simplest D&C algorithm: divide by 2, conquer one half (discard the other), combine step is trivial. T(n) = T(n/2) + O(1) = O(log n). Master theorem Case 2 with a=1, b=2.

What makes binary search special among D&C algorithms is that it only recurses into one subproblem (a=1). This is why it is logarithmic — each step cuts the search space in half without creating any additional work. Compare with merge sort (a=2): two subproblems of half size create linear work per level. One subproblem of half size creates constant work per level.

python
def binary_search(A, target):
    """D&C perspective: divide by 2, conquer 1 half, combine trivially."""
    lo, hi = 0, len(A) - 1
    while lo ≤ hi:
        mid = (lo + hi) // 2        # Divide: find midpoint
        if A[mid] == target:
            return mid                # Found it
        elif A[mid] < target:
            lo = mid + 1              # Conquer: discard left half
        else:
            hi = mid - 1              # Conquer: discard right half
    return -1                        # Combine: nothing (trivial)

The iterative version above is equivalent to the recursive D&C formulation — we just unroll the tail recursion into a loop. This is a common optimization: when the recursion only goes into one branch (tail recursion), convert it to iteration to save stack space.

FFT: The Crown Jewel of D&C

The Fast Fourier Transform evaluates a polynomial of degree n at n roots of unity in O(n log n) time, versus the naive O(n²). It splits the polynomial into even and odd coefficients (divide), recursively evaluates each half (conquer), and combines using the butterfly pattern (combine). T(n) = 2T(n/2) + O(n) = O(n log n).

Why does FFT matter? Because polynomial multiplication is secretly behind everything:

The D&C structure of FFT is beautiful: a polynomial P(x) = a₀ + a₁x + a₂x² + ... + a_n-1x^n-1 splits into even powers P_even(x²) = a₀ + a₂x² + a₄x⁴ + ... and odd powers P_odd(x²) = a₁ + a₃x² + a₅x⁴ + ..., so P(x) = P_even(x²) + x · P_odd(x²). Two half-size FFTs plus O(n) combining. Same recurrence as merge sort. We will cover FFT in full depth in a later chapter (CLRS Ch 30).

Chapter 8: Interview Arsenal

Master Theorem Cheat Sheet

D&C Algorithm Zoo

Coding Drill 1: pow(x, n)

Compute xⁿ in O(log n) time using the D&C insight: xⁿ = (x^n/2)² if n is even, x · x^n-1 if n is odd.

python
def power(x, n):
    """Compute x^n in O(log n) multiplications."""
    if n == 0: return 1
    if n < 0: return 1 / power(x, -n)
    if n % 2 == 0:
        half = power(x, n // 2)
        return half * half       # 1 multiplication, not 2
    else:
        return x * power(x, n - 1)

Coding Drill 2: Count Inversions

An inversion is a pair (i, j) where i < j but A[i] > A[j]. Counting inversions measures how far an array is from sorted. Brute force: O(n²). D&C (modified merge sort): O(n log n). The trick: count cross-inversions during the merge step.

python
def count_inversions(A):
    if len(A) ≤ 1:
        return A, 0
    mid = len(A) // 2
    left, l_inv = count_inversions(A[:mid])
    right, r_inv = count_inversions(A[mid:])
    merged, split_inv = merge_count(left, right)
    return merged, l_inv + r_inv + split_inv

def merge_count(L, R):
    result, inv = [], 0
    i = j = 0
    while i < len(L) and j < len(R):
        if L[i] ≤ R[j]:
            result.append(L[i]); i += 1
        else:
            result.append(R[j]); j += 1
            inv += len(L) - i  # all remaining left elements are inversions
    result.extend(L[i:]); result.extend(R[j:])
    return result, inv

Coding Drill 3: Search in Rotated Sorted Array

python
def search_rotated(A, target):
    """Find target in rotated sorted array, O(log n)."""
    lo, hi = 0, len(A) - 1
    while lo ≤ hi:
        mid = (lo + hi) // 2
        if A[mid] == target:
            return mid
        if A[lo] ≤ A[mid]:  # left half is sorted
            if A[lo] ≤ target < A[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:               # right half is sorted
            if A[mid] < target ≤ A[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Coding Drill 4: Merge Sort to Count Inversions

Coding Drill 5: Median of Two Sorted Arrays

Given two sorted arrays of size m and n, find the median of the combined array in O(log(min(m,n))) time. This is one of the hardest D&C interview problems (LeetCode Hard).

The key insight: the median divides the combined array into two equal halves. We binary search for the correct partition point in the smaller array, then compute the partition in the larger array.

python
def find_median(A, B):
    """Find median of two sorted arrays in O(log(min(m,n)))."""
    if len(A) > len(B):
        A, B = B, A  # ensure A is shorter
    m, n = len(A), len(B)
    lo, hi = 0, m

    while lo ≤ hi:
        i = (lo + hi) // 2       # partition A at i
        j = (m + n + 1) // 2 - i  # partition B at j

        left_A  = A[i-1] if i > 0 else float('-inf')
        right_A = A[i]   if i < m else float('inf')
        left_B  = B[j-1] if j > 0 else float('-inf')
        right_B = B[j]   if j < n else float('inf')

        if left_A ≤ right_B and left_B ≤ right_A:
            if (m + n) % 2 == 0:
                return (max(left_A, left_B) + min(right_A, right_B)) / 2
            return max(left_A, left_B)
        elif left_A > right_B:
            hi = i - 1
        else:
            lo = i + 1

Coding Drill 6: Kth Largest Element (Quickselect)

Quickselect finds the k-th smallest element in O(n) average time using D&C — partition around a random pivot, then recurse into only the half that contains the target rank. Unlike quicksort, we recurse into one side, not both.

python
import random

def quickselect(A, k):
    """Find k-th smallest element (0-indexed). Average O(n)."""
    if len(A) == 1:
        return A[0]
    pivot = random.choice(A)
    lows  = [x for x in A if x < pivot]
    highs = [x for x in A if x > pivot]
    pivots = [x for x in A if x == pivot]
    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows) + len(pivots):
        return pivot
    else:
        return quickselect(highs, k - len(lows) - len(pivots))

The recurrence is T(n) = T(n/2) + O(n) on average (we recurse into one half). By the master theorem: a=1, b=2, f(n)=n, n^log₂1 = 1. Since f(n) = n polynomially dominates 1, Case 3 gives T(n) = O(n). Key: we recurse into only ONE subproblem, not two.

The worst case is O(n²) (always picking the min or max as pivot), but randomization makes this astronomically unlikely. The median-of-medians algorithm (CLRS Ch 9) guarantees O(n) worst case by choosing a "good enough" pivot deterministically — split into groups of 5, find median of each, then recursively find the median of those medians.

The Power of Reducing Subproblems

A recurring theme in this chapter: the number of subproblems a is the most important factor in D&C complexity. Let us see this concretely for T(n) = aT(n/2) + n:

Going from a=8 to a=7 (Strassen) reduces the work for n=1024 by nearly 4x. Going from a=4 to a=3 (Karatsuba) reduces it by 18x. Every saved subproblem pays exponential dividends. This is why researchers have spent decades trying to reduce the matrix multiplication constant from 7 to lower values — each reduction compounds across all recursion levels.

The Five Interview Dimensions for D&C

D&C Time Complexity Quick Reference

For rapid recall during interviews. Every entry here should be instant for you:

Common D&C Interview Mistakes

Coding Drill 7: Matrix Exponentiation via D&C

Just as pow(x, n) computes scalar exponentiation in O(log n), we can compute matrix exponentiation Mⁿ in O(k³ log n) time, where k is the matrix dimension. This is critical for computing the n-th Fibonacci number in O(log n):

python
import numpy as np

def matrix_power(M, n):
    """Compute M^n in O(k^3 log n) using repeated squaring."""
    k = M.shape[0]
    result = np.eye(k, dtype=int)  # identity matrix
    base = M.copy()
    while n > 0:
        if n % 2 == 1:
            result = result @ base
        base = base @ base  # square the base
        n //= 2
    return result

# Fibonacci via matrix exponentiation
# [F(n+1), F(n)] = [[1,1],[1,0]]^n * [F(1), F(0)]
def fibonacci(n):
    if n ≤ 1: return n
    M = np.array([[1, 1], [1, 0]])
    result = matrix_power(M, n - 1)
    return result[0][0]

print(fibonacci(50))  # 12586269025 (in O(log 50) matrix mults)

This technique extends to any linear recurrence: if x_n depends linearly on the previous k terms, you can express it as a k×k matrix raised to the n-th power. D&C (repeated squaring) makes this O(k³ log n) instead of the naive O(kn).

Coding Drill 8: Number of Inversions (Variant: Significant Inversions)

A significant inversion is a pair (i, j) where i < j and A[i] > 2·A[j]. This cannot be counted during the standard merge step because the "2x" condition breaks the merge invariant. Instead, count significant inversions in a separate pass before merging:

python
def count_significant(A):
    """Count pairs (i,j) where i<j and A[i] > 2*A[j]. O(n log n)."""
    if len(A) ≤ 1:
        return A, 0
    mid = len(A) // 2
    left, l_inv = count_significant(A[:mid])
    right, r_inv = count_significant(A[mid:])

    # Count cross-significant inversions (before merge)
    count = 0
    j = 0
    for i in range(len(left)):
        while j < len(right) and left[i] > 2 * right[j]:
            j += 1
        count += j  # all right[0..j-1] form significant inversions with left[i]

    # Standard merge (for the recursive structure)
    merged = []
    a = b = 0
    while a < len(left) and b < len(right):
        if left[a] ≤ right[b]:
            merged.append(left[a]); a += 1
        else:
            merged.append(right[b]); b += 1
    merged.extend(left[a:]); merged.extend(right[b:])

    return merged, l_inv + r_inv + count

This "count before merge" pattern is a common interview variant. The key insight: because both halves are sorted, the counting loop uses two pointers and runs in O(n), keeping the total at O(n log n).

D&C Problem Recognition Patterns

In interviews, these signals suggest a D&C approach:

Chapter 9: Connections

Divide-and-conquer is one of four major algorithm design paradigms in CLRS. Here is how they relate:

Where D&C Appears Next in CLRS

• Chapter 2: Merge sort — the D&C algorithm that introduced us to the paradigm
• Chapter 7: Quicksort — D&C with expensive divide and trivial combine
• Chapter 9: Order statistics — selection in O(n) using median-of-medians
• Chapter 15: Dynamic programming — what happens when D&C has overlapping subproblems
• Chapter 30: FFT — the crown jewel of D&C in applied mathematics
• Chapter 33: Computational geometry — closest pair, convex hull via D&C

The Big Picture

D&C vs DP: The Decision Flowchart

The most common algorithm design interview question is: "Should I use D&C or DP?" Here is a concrete decision procedure:

You now have three tools for analyzing any D&C recurrence T(n) = aT(n/b) + f(n):

And you have seen D&C applied to four domains: sorting (merge sort), optimization (max subarray), linear algebra (Strassen), and number theory (Karatsuba). The pattern is always the same: divide, conquer, combine. What changes is where the cleverness lives — in the divide step, the combine step, or in reducing the number of subproblems.

What We Learned

The single most important skill from this chapter is writing and solving recurrences. Every algorithm in the next 20 chapters of CLRS builds on this foundation. When you encounter a new algorithm, your first question should be: "What is the recurrence?" and your second should be: "Which master theorem case does it fall into?"

Limits of Divide-and-Conquer

D&C is not always the right tool. Here are situations where it fails or underperforms:

The best real-world algorithms are hybrids. Python's Timsort uses insertion sort for small runs and merge sort for combining them. BLAS uses Strassen for large matrices and tiled naive for small ones. Quicksort implementations use insertion sort below n ≈ 16. Always think about the crossover point — the input size where the asymptotically faster algorithm actually becomes faster in wall-clock time.

D&C in the Real World