Divide and Conquer

In the previous lesson, brute force ran as a single piece and saw every possibility. The first design approach breaks this wholeness: it reduces the problem to two smaller copies of the same kind, solves each recursively, and combines the two solutions. This approach is called divide and conquer.

The Algorithms course already measured three examples of this approach: merge sort, quicksort, and binary search. This lesson does not repeat those procedures. What it measures is the recurrence itself, and the question it asks is this: splitting and combining are separate calculations; on how many inputs does a wrong answer appear when the combine step is left incomplete, and where does the input size end at which splitting saves no steps.

• DA11. The measured problem: the contiguous subarray with the largest sum in an array. The subarray cannot be empty, so in the worst case the answer is a single element.
• DA12. The oracle sees every contiguous subarray; a 12-element array has 78 subarrays.
• DA13. A step is adding an element to a sum and comparing it. The recursive call itself is also a step and is counted separately.
• DA14. The split rule is the same in every variant: the array is divided in half, so $a = 2$ and $b = 2$ in the recurrence.
• DA15. Combining is measured in three variants — linear, quadratic, incomplete. All three use the same split; the only difference between them is the combine step.
• DA16. The approach’s precondition: the combine step must also cover the solution’s form that crosses the boundary. Incomplete combining breaks only this precondition.
• DA17. The length sweep doubles from 2 to 128; each length still has 40 arrays.
• DA18. The sorting and search procedures from M01/K04 are not repeated; the measure here is the recurrence itself.
• DA19. Every measurement is also run on a second corpus with seed 20260219.

The Recurrence of Splitting

A divide-and-conquer procedure consists of three tasks: splitting the problem into $a$ parts, solving each part recursively, and combining the parts’ solutions. If the parts are $1/b$ the size of the original problem, the cost satisfies this recurrence:

$$T(n) = a \cdot T(n/b) + f(n)$$

Here $f(n)$ is the cost of combining, and it also includes the splitting itself. The master theorem gives the solution of this recurrence by looking at the race between $f(n)$ and $n^{\log_b a}$. There are three cases: if combining is cheaper than the recursion, cost is determined by the recursion and the result is $\Theta(n^{\log_b a})$; if the two are of the same magnitude, a $\log n$ factor enters and the result is $\Theta(n^{\log_b a} \log n)$; if combining dominates, the result is directly $\Theta(f(n))$.

In this lesson’s split, $a = 2$, $b = 2$, and $\log_b a = 1$. So the race is over whether combining is linear. Linear combining falls into the second case and gives $\Theta(n \log n)$; quadratic combining falls into the third case and gives $\Theta(n^2)$ — that is, the same magnitude as brute force. The split does not change, yet the result does; this is the formal expression of splitting and combining being separate calculations. A limit of the master theorem should also be noted here: if the parts are not of equal size, or if $f(n)$ falls into none of the three cases, the theorem gives no answer, and the recurrence must be solved by direct expansion. Because this lesson’s split is equal, that case is not encountered.

The Oracle and the Problem

The measured problem is the plainest one where a boundary-crossing solution exists: the contiguous subarray with the largest sum. The oracle counts every subarray.

# Shared framework: corpus and step counter (same as the previous lesson).
SEED = 20260218


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corpus(seed=SEED, n=40, length=12):
    r = generator(seed)
    return [{"no": i + 1, "array": [r(30) - 9 for _ in range(length)]}
            for i in range(n)]


class Counter:
    def __init__(self):
        self.steps = 0

    def add(self, n=1):
        self.steps += n


def oracle_max(array, s):
    """Sees every contiguous subarray. This is the oracle."""
    best = array[0]
    for i in range(len(array)):
        total = 0
        for j in range(i, len(array)):
            s.add()
            total += array[j]
            if total > best:
                best = total
    return best


items = corpus()
s = Counter()
answers = [oracle_max(k["array"], s) for k in items]
print("corpus:", len(items), "arrays x 12 values | oracle total steps:", s.steps)
print("steps per array:", s.steps // len(items), "= 12 x 13 / 2")
print("first three answers:", answers[:3])

corpus: 40 arrays x 12 values | oracle total steps: 3120
steps per array: 78 = 12 x 13 / 2
first three answers: [52, 55, 84]

The oracle spends 78 steps per array, 3120 steps on forty arrays, and this does not change with the input. The size of the answers is also meaningful: 52, 55, and 84 for the first three arrays. Since the corpus’s values are at most 20, these answers must span more than one element; the solution is almost never a single element.

Three Combine Steps, One Split

The procedure below carries three variants in a single body. The split is the same in all three; the only thing that changes is how the boundary-crossing solution is computed.

# Continuing from the previous block: corpus, Counter and items come from there.
def divide_conquer(array, s, combine="linear"):
    """T(n) = 2 T(n/2) + combine(n). The combine step finds the BOUNDARY-CROSSING solution."""
    def solve(start, end):
        s.add()                                   # the recursive call is also a step
        if end - start == 1:
            return array[start]
        mid = (start + end) // 2
        left = solve(start, mid)
        right = solve(mid, end)
        if combine == "incomplete":               # BOUNDARY-CROSSING SOLUTION IS SKIPPED
            return max(left, right)
        if combine == "quadratic":                # correct but expensive combining
            left_sums, t = [], 0
            for i in range(mid - 1, start - 1, -1):
                s.add()
                t += array[i]
                left_sums.append(t)
            right_sums, t = [], 0
            for j in range(mid, end):
                s.add()
                t += array[j]
                right_sums.append(t)
            best = None
            for a in left_sums:                   # every boundary pair is tried separately
                for b in right_sums:
                    s.add()
                    if best is None or a + b > best:
                        best = a + b
            return max(left, right, best)
        best_left, t = None, 0                    # linear combining
        for i in range(mid - 1, start - 1, -1):
            s.add()
            t += array[i]
            if best_left is None or t > best_left:
                best_left = t
        best_right, t = None, 0
        for j in range(mid, end):
            s.add()
            t += array[j]
            if best_right is None or t > best_right:
                best_right = t
        return max(left, right, best_left + best_right)
    return solve(0, len(array))


def measure(combine, items):
    diverging, approach_total, oracle_total = [], 0, 0
    for k in items:
        s1, s2 = Counter(), Counter()
        if divide_conquer(k["array"], s1, combine) != oracle_max(k["array"], s2):
            diverging.append(k["no"])
        approach_total += s1.steps
        oracle_total += s2.steps
    return {"diverging": len(diverging), "diverging_no": diverging[:6],
            "approach_steps": approach_total, "oracle_steps": oracle_total,
            "ratio": round(oracle_total / approach_total, 2)}


for name in ("linear", "quadratic", "incomplete"):
    print(f"{name:10s} combining:", measure(name, items))

linear     combining: {'diverging': 0, 'diverging_no': [], 'approach_steps': 2680, 'oracle_steps': 3120, 'ratio': 1.16}
quadratic  combining: {'diverging': 0, 'diverging_no': [], 'approach_steps': 5320, 'oracle_steps': 3120, 'ratio': 0.59}
incomplete combining: {'diverging': 40, 'diverging_no': [1, 2, 3, 4, 5, 6], 'approach_steps': 920, 'oracle_steps': 3120, 'ratio': 3.39}

Three numbers side by side. The oracle: 3120 steps. Linear combining spends 2680 steps — 1.16 times fewer than the oracle — and diverges on none of the 40 inputs. Quadratic combining spends 5320 steps, that is, 1.71 times slower than the oracle, and it too does not diverge on any of the 40 inputs. Incomplete combining spends 920 steps, 3.39 times fewer than the oracle, and diverges on 40 of the 40 inputs.

Two readings stand together. First: being correct does not require being fast. Quadratic combining always gives the correct answer but is slower than brute force; here splitting gains nothing, and on top of that it adds the recursive calls’ own steps. Second: being fast does not require being correct. Incomplete combining is the cheapest and looks tempting for exactly that reason; yet its answer is wrong on all 40 inputs.

Looking at what the incomplete variant returns shows the shape of the error. Once the boundary-crossing solution is skipped, recursion descends to the leaves and, at every level, the better of the two halves is taken; the only candidate left is the array’s largest single element. While the oracle’s first three answers are 52, 55, and 84, incomplete combining’s answer can be at most 20. The error is not a computational mistake but a region of the solution space that is never visited — the same shape as the previous lesson’s sampling error, this time at the recursion boundary.

As the Recurrence Turns into Numbers

The master theorem’s two cases become visible in the measured step count as the length grows.

# Continuing from the previous blocks: corpus, Counter, oracle_max, divide_conquer come from there.
print("length  oracle steps  linear steps  ratio  quadratic steps  ratio")
for length in (2, 4, 8, 16, 32, 64, 128):
    items = corpus(length=length)
    s1, s2, s3 = Counter(), Counter(), Counter()
    for k in items:
        oracle_max(k["array"], s1)
        divide_conquer(k["array"], s2, "linear")
        divide_conquer(k["array"], s3, "quadratic")
    print(f"{length:6d} {s1.steps:13d} {s2.steps:13d} {s1.steps / s2.steps:6.2f}"
          f" {s3.steps:16d} {s1.steps / s3.steps:6.2f}")

length  oracle steps  linear steps  ratio  quadratic steps  ratio
     2           120           200   0.60              240   0.50
     4           400           600   0.67              840   0.48
     8          1440          1560   0.92             2680   0.54
    16          5440          3800   1.43             8600   0.63
    32         21120          8920   2.37            28760   0.73
    64         83200         20440   4.07           101080   0.82
   128        330240         46040   7.17           371160   0.89

Linear combining’s ratio rises from 0.60 to 7.17 and crosses 1 between 8 and 16. The meaning is clear: splitting gains nothing up to 8 elements — on the contrary, it costs. At length 2, divide and conquer spends almost twice as many steps as the oracle; the gain only starts at 16. The loss comes from the recursive calls — an $n$-element array makes $2n - 1$ calls, and none of these exist in brute force. This is the measured reason real implementations cut off recursion on small segments and switch to a direct solution.

Quadratic combining’s ratio, in contrast, stays between 0.50 and 0.89 and never crosses 1 at any length. The ratio slowly approaches 1, because both procedures grow as $\Theta(n^2)$ and the difference between them is a constant factor. This is exactly the master theorem’s third case: when combining dominates, the $\log n$ gain from splitting disappears, and only the recursion’s overhead remains. Splitting is not a gain by itself; it is a gain only if combining is cheap.

Splitting the total step count into two components makes the master theorem’s second case directly visible.

# Continuing from the previous blocks: corpus, Counter and divide_conquer come from there.
from math import log2
print("length  calls  combining  total per array   n x log2(n)")
for length in (8, 16, 32, 64, 128):
    items = corpus(length=length)
    s = Counter()
    for k in items:
        divide_conquer(k["array"], s, "linear")
    calls = 2 * length - 1
    total = s.steps // len(items)
    print(f"{length:6d} {calls:6d} {total - calls:11d} {total:18d}"
          f" {int(length * log2(length)):13d}")

length  calls  combining  total per array   n x log2(n)
     8     15          24                 39            24
    16     31          64                 95            64
    32     63         160                223           160
    64    127         384                511           384
   128    255         896               1151           896

The combining column and the last column are exactly the same: 24, 64, 160, 384, 896. The recurrence’s solution here is not an approximation but a counted equality — at every level, a total of $n$ steps is spent, and there are $\log_2 n$ levels. The calls column, by contrast, grows separately as $2n - 1$ and is linear; this is the component that dominates at small $n$ and becomes negligible at large $n$. At length 8, calls take up 38% of the total; at 128, 22%. This ratio is exactly the numerical source of splitting’s loss on small inputs.

The Second Corpus

# Continuing from the previous blocks: corpus, measure come from there.
SECOND = 20260219
for label, seed in (("first corpus (20260218)", SEED),
                    ("second corpus (20260219)", SECOND)):
    items = corpus(seed)
    print(label)
    for name in ("linear", "incomplete"):
        o = measure(name, items)
        print(f"  {name:10s} diverging {o['diverging']:2d} / 40 | ratio",
              round(o["diverging"] / 40, 4), "| approach steps", o["approach_steps"])

first corpus (20260218)
  linear     diverging  0 / 40 | ratio 0.0 | approach steps 2680
  incomplete diverging 40 / 40 | ratio 1.0 | approach steps 920
second corpus (20260219)
  linear     diverging  0 / 40 | ratio 0.0 | approach steps 2680
  incomplete diverging 39 / 40 | ratio 0.975 | approach steps 920

Linear combining’s step count is exactly the same in both corpora: 2680. This is not surprising, because this procedure’s step count depends only on length, not on the values — neither brute force nor divide and conquer has an early exit. Incomplete combining’s diverging count drops from 40 to 39; the ratio from 1.0000 to 0.9750. The difference is one input and below the resolution, so it is considered unmeasured. In the second corpus, the one array that does not diverge is the ninth: ten of its twelve values are zero or negative, and its single large value, 20, is both the largest element and the largest subarray sum. There, incomplete combining gives the correct answer for the wrong reason — it still never searched for the boundary-crossing solution; what it looked for this time happened, this time, to be enough. An approach agreeing with the oracle on a single input does not mean its precondition holds; this is why the measure is taken over 40 inputs.

Summary

• The divide-and-conquer recurrence is $T(n) = a \cdot T(n/b) + f(n)$; in this lesson $a = 2$, $b = 2$, and $f(n)$ is the only thing that determines the result.
• On the same split, linear combining spends 2680 steps — 1.16 times fewer than the oracle — and is correct on all 40 inputs; quadratic combining spends 5320 steps, 1.71 times slower than the oracle, but is still correct.
• Incomplete combining, which skips the boundary-crossing solution, is the cheapest at 920 steps and is wrong on 40 of the 40 inputs; what it returns is the array’s largest single element.
• Splitting gains nothing up to 8 elements; the ratio crosses 1 between 8 and 16, and the loss comes from $2n - 1$ recursive calls.
• With quadratic combining, the ratio never crosses 1 at any length; in the master theorem’s third case, splitting’s $\log n$ gain disappears.
• On the second corpus, linear combining’s step count is exactly the same; incomplete combining’s diverging count is 39 instead of 40; the one-input difference is below the resolution.

Next Step

Divide and conquer split the problem and solved every part. The next approach does something bolder: it makes a single choice at every step and never goes back. This boldness sometimes has a proof — as with the three greedy procedures in the Algorithms course — and sometimes does not. The next lesson counts when greedy choice is wrong: on how many four-value coin systems greedy gives more coins than necessary.