--- title: 'Divide and Conquer' source: 'https://academia.sh/en/courses/advanced-algorithms/divide-and-conquer' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:25+00:00' license: 'CC BY-SA 4.0' --- # Divide and Conquer Splitting and combining are separate calculations: on the same split, linear combining spends 1.16 times fewer steps than the oracle and stays correct on all 40 inputs, while quadratic combining is 1.71 times slower than the oracle, and incomplete combining, which skips the boundary-crossing solution, gives a wrong answer on 40 of 40 inputs with 920 steps. 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. ```python # 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. ```python # 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. ```python # 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. ```python # 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 ```python # 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.