Divide & Conquer

By the end of this lesson you will be able to solve a problem by splitting it into smaller copies of itself (divide-and-conquer), trace the maximum-subarray algorithm and Strassen's matrix-multiplication trick line by line, and — most importantly — solve a recurrence for a divide-and-conquer algorithm's running time using three different methods: substitution, recursion trees, and the master method.

0. What is divide-and-conquer?

Imagine you must count every page in a 10,000-page warehouse of documents. Counting one page at a time would take forever. Instead: split the warehouse in half, hand each half to a helper, and tell each helper to do the exact same thing — split their half again and hand it off — until a helper is looking at a single shelf small enough to just count by hand. Then every pair of helpers adds their two sub-totals together, all the way back up. That is divide-and-conquer: divide the problem into smaller subproblems of the same kind, conquer each subproblem (recursively, or directly if it's small enough to be a base case), then combine the subproblem answers into the answer for the original problem.

A divide-and-conquer algorithm's running time is described by a recurrence: an equation that defines the cost T(n) for input size n in terms of T on smaller inputs. For example, an algorithm that splits its input of size n into two halves, recurses on each, and does Θ(n) work to combine the results, has the recurrence T(n) = 2T(n/2) + Θ(n). Two cautions: a subproblem that is not a smaller instance of the same problem (like the crossing-subarray search in section 1) is solved as part of the combine step; and a recursion that only shrinks the input by one element — recursive linear search, T(n) = T(n − 1) + Θ(1) — is still a recurrence, but it is not of the master form aT(n/b) + f(n); it is just linear recursion.

Dart — recurrence(n, a, b, f, memo) is “T(n) = a·T(n/b) + f(n), T(1) = 1” written as recursion + memo. For T(n) = 2T(n/2) + n it equals the closed form n·lg n + n for every n = 2^k up to 2²⁰ (T(8) = 8·3 + 8 = 32); T(n) = T(n/2) + 1 gives lg n + 1; T(n) = 3T(n/2) + n gives 3n^{lg 3} − 2n; and tLinear shows that a recursion that shrinks by one, T(n) = T(n−1) + T(1) + 1, is just 2n − 1 (linear — not of the form aT(n/b) + f(n)).

Input size → what is feasible: the memoised recursion is Θ(lg n) calls for n = b^k (n up to 2⁶² is fine); tLinear recurses n deep, so keep n ≤ ~10⁴ (Dart’s default stack).

This chapter teaches you two worked divide-and-conquer algorithms (the maximum-subarray problem and Strassen's matrix multiplication), then three general-purpose techniques for turning a recurrence like T(n) = 2T(n/2) + Θ(n) into a closed-form answer like Θ(n lg n): the substitution method, the recursion-tree method, and the master method.

Divide-and-conquer = divide into smaller same-kind subproblems + conquer each (recursively or by a base case) + combine. Its running time is captured by a recurrence T(n) = a·T(n/b) + f(n), which this chapter teaches you to solve three ways.

1. The maximum-subarray problem

Picture a stock's daily price as a jagged line. You may buy on exactly one day and sell on exactly one later day, and you want the biggest possible profit. The trick: instead of thinking about prices, look at the array of day-to-day changes (today's price minus yesterday's). Buying on day i and selling on day j now earns exactly the sum of the changes from day i+1 through day j. So "best buy/sell days" becomes "find the contiguous run of numbers in this array of changes with the biggest possible sum" — the maximum subarray problem. (It's only interesting when the array can have negative numbers — otherwise the whole array is always the answer.)

A first idea: try every pair of start/end days and sum each one. There are C(n,2) = Θ(n²) pairs, so this brute-force approach costs Θ(n²) (or Θ(n³) if you re-sum from scratch for each pair instead of reusing the running total). Divide-and-conquer does better: Θ(n lg n).

Dart — the brute force, 0-indexed like all Dart lists: i runs over 0..n−1, and the inner loop starts at j = i because a one-element subarray is allowed. It tracks (low, high, sum) in a record.

Input size → what is feasible: n ≤ 3·10³ → n²/2 = 4.5·10⁶ steps, instant; n = 2·10⁵ → 2·10¹⁰ steps (~200 s) — too slow, use findMaximumSubarray (n lg n) or Kadane (n).

Split the array A[low..high] at its midpoint mid. Any contiguous subarray falls into exactly one of three places: (1) entirely in the left half A[low..mid], (2) entirely in the right half A[mid+1..high], or (3) crossing the midpoint, using some suffix of the left half and some prefix of the right half. The best of the left, the best of the right, and the best crossing subarray — whichever of those three is biggest — is the overall answer. Left and right are solved by recursing; crossing needs its own separate, linear-time helper because it isn't a smaller version of the same problem.

findMaxCrossingSubarray

This helper takes an already-fixed midpoint and finds the best subarray that uses at least one element from each side. It scans left from mid down to low, keeping a running sum and remembering the best "ends exactly at mid" sum seen so far — then does the mirror-image scan to the right. Both scans are Θ(n), so this whole helper is Θ(n).

Dart — findMaxCrossingSubarray in Dart. The page’s 16-number array is a[0..15], so the whole-array call is (low, mid, high) = (0, 7, 15); on that array it returns low = 1, high = 10, sum = 10 (checked in verify/c04.dart). The two scans are the two for loops; sum > leftSum with a strict > keeps the maximum closest to the midpoint when several tie.

Input size → what is feasible: Θ(high − low + 1) per call: n = 10⁶ elements is a few ms; it is called once per node of the recursion tree below.

A crossing subarray must include element A[mid] and element A[mid+1] — it can't skip the midpoint. That's exactly why the left scan stops at mid (not before it) and the right scan starts at mid+1 (not after it): together they guarantee the two halves are glued directly across the middle with no gap.

findMaximumSubarray

The full divide-and-conquer algorithm: base case is a single element (a subarray of length 1 is trivially its own maximum subarray); otherwise split in half, recurse on both halves, run findMaxCrossingSubarray once, and return whichever of the three candidates has the biggest sum.

Dart — findMaximumSubarray in Dart. The midpoint ⌊(low + high)/2⌋ is (low + high) ~/ 2 (~/ is integer division; both indices are ≥ 0, so it equals the floor). The base case is low == high, the two recursive calls plus the crossing call build the three candidates, and the three-way comparison picks the winner; ties prefer left, then right.

Input size → what is feasible: Θ(n lg n): n = 2·10⁵ → ≈ 3.5·10⁶ steps (instant), n = 10⁷ → ≈ 2.3·10⁸ (seconds) → use Kadane there. Recursion depth ⌈lg n⌉ ≤ 24 for any n ≤ 10⁷.

Recurrence: T(n) = 2T(n/2) + Θ(n) — two half-size recursive calls plus Θ(n) work for the crossing check and the 3-way comparison. We'll prove with the master method later in this chapter that this solves to Θ(n lg n) — exactly like merge sort's recurrence, because the shape (two half-size subproblems + linear combine) is identical.

Kadane's algorithm — linear time

There's an even faster, non-divide-and-conquer approach worth knowing, because interviewers ask for it constantly. The key insight: the best subarray ending exactly at index j+1 is either just A[j+1] by itself, or (the best subarray ending at j) extended one step further to include A[j+1] — whichever is bigger. Track that "best-ending-here" sum as you walk left to right once, and remember the best value it ever reaches. One pass, Θ(n) time, O(1) extra space.

Dart — Kadane’s algorithm in Dart. curSum is the best sum of a subarray ending exactly at index i: restart at a[i] when the old run is negative (curSum < 0), otherwise extend it; curLow remembers where that run started and best… keeps the best run ever seen.

Input size → what is feasible: Θ(n) with O(1) extra space: n = 10⁶–10⁷ elements is a single pass, well under a second.

Divide-and-conquer max subarray: Θ(n lg n) via T(n)=2T(n/2)+Θ(n). Kadane's algorithm: Θ(n), one pass. On an all-negative array, both correctly return the single largest (least negative) element — there's no rule that a "subarray" must be non-empty and contain a positive number, so the best you can do is pick the best single element.

Dart — the step counters behind the three bounds. bruteSteps(n) = n(n+1)/2; dcSteps mirrors the recursion (a base-case read, or two half calls plus the crossing scan reading high − low + 1 elements) and equals n·lg n + n for n = 2^k; kadaneSteps(n) = n. For n = 16: 136 / 80 / 16 reads; for n = 1024: 524,800 / 11,264 / 1,024.

Input size → what is feasible: n ≤ 10³: all three are instant; n = 10⁵: brute force is already 5·10⁹ reads — the gap is the whole point of the chapter.

2. Strassen's algorithm for matrix multiplication

Multiplying two n×n matrices the obvious way is like paying every worker in a factory to redo their multiplication from scratch for every single output cell — n multiplications per cell, n² cells, Θ(n³) total. Strassen's insight (1969) was that if you're clever about which sums and differences you compute first, several of the matrix multiplications you'd otherwise need become redundant — you can get away with fewer, bigger multiplication "batches" that do more work per multiplication.

Dart — the matrix helpers every method below uses (0-indexed): _quad(m, rowOff, colOff, size) copies one (n/2)×(n/2) block — A11 = _quad(a, 0, 0, h), A12 = _quad(a, 0, h, h), A21 = _quad(a, h, 0, h), A22 = _quad(a, h, h, h) with h = n/2 — and _place writes a block back. A tuned library passes index offsets in Θ(1) instead; this copy costs Θ(n²), which the Θ(n²) combine step already pays, so the recurrences below do not change.

Input size → what is feasible: each helper is Θ(n²) per call (n = 1000 → 10⁶ cells, instant).

squareMatrixMultiply (the naive triple loop)

C[i][j] = Σₖ A[i][k]·B[k][j] for every cell — three nested loops, Θ(n³).

Dart — squareMatrixMultiply: the three nested loops, i = row of A, j = column of B, k = the shared index, i.e. c_ij = Σ_k a_ik·b_kj (indices 0..n−1).

Input size → what is feasible: Θ(n³): n ≤ 500 → 1.25·10⁸ multiplications, about a second at most; n = 5000 → 1.25·10¹¹ — too slow without blocking or a hybrid.

squareMatrixMultiplyRecursive

Split each n×n matrix into four (n/2)×(n/2) quadrants (assume n is a power of 2). Then C = A·B can be written purely in terms of the quadrants: C11 = A11·B11 + A12·B21, and similarly for C12, C21, C22 — 8 quadrant multiplications and 4 quadrant additions in total.

One 2×2 example only shows one recursion level ending immediately in the base case. Let's see it one level deeper on a 4×4 matrix, check the smallest possible input (1×1, no recursion at all), and then let you try your own numbers:

Dart — squareMatrixMultiplyRecursive in Dart: n == 1 is the base case, h = n ~/ 2, the eight squareMatrixMultiplyRecursive calls are the eight quadrant products, and the four _add calls build C11, C12, C21, C22 before _place glues them together.

Input size → what is feasible: n must be a power of 2; n ≤ 128 runs in about 0.1 s (Θ(n³) — no faster than the triple loop, as the pitfall below explains); recursion depth lg n ≤ 7.

This recursive version does not beat the naive algorithm: its recurrence is T(n) = 8T(n/2) + Θ(n²), which (by the master method, case 1) is still Θ(n³) — the branching factor a=8 makes the recursion tree exactly as bushy as the naive triple loop. Asymptotic notation absorbs constant factors multiplied onto a term, but it does not hide the branching factor a inside aT(n/b) — that number directly controls how many leaves the recursion tree ends up with.

Strassen's method

Strassen's trick reduces those 8 quadrant multiplications to 7, at the cost of a few extra additions/subtractions (which are only Θ(n²) and don't change the recursion's branching factor). The 7 products are each computed from sums or differences of quadrants (not the raw quadrants themselves), and then combined with more additions/subtractions to recover the four output quadrants.

Dart — Strassen’s trick on a 2×2 matrix of plain numbers: the ten sums/differences t1..t10, the seven products m1..m7 and the four outputs C11 = m1 + m4 − m5 + m7, C12 = m3 + m5, C21 = m2 + m4, C22 = m1 − m2 + m3 + m6. On the page’s A = [[3,1],[2,4]], B = [[5,2],[1,6]] it returns [[16,12],[14,28]], and it agrees with the triple loop on 300 random 2×2 pairs (verify/c04.dart).

Input size → what is feasible: O(1) here (7 multiplications instead of 8); the saving only pays off when the blocks are big matrices, see the next panel.

Again, one 2×2 example ends immediately in the base case. Here is the same trick one level deeper on a 4×4 matrix (showing all 10 t sums and all 7 m products at the top level), the 1×1 base case on its own, and a box to try your own matrices:

Dart — strassen in Dart: t1…t10 are the ten sums and differences of blocks (A11 → a11, and so on), m1…m7 are the seven recursive products (the only recursive calls), and c11…c22 are the four combine lines.

Input size → what is feasible: n a power of 2, n ≤ 256 → 7⁸ = 5,764,801 scalar products (under a second on a laptop); real libraries stop the recursion near n = 64 and use the triple loop below that, because Strassen’s overheads dominate at small n.

Recurrence: T(n) = 7T(n/2) + Θ(n²), which the master method (case 1, worked out later in this lesson) solves to T(n) = Θ(n^lg7) ≈ Θ(n^2.807) — asymptotically better than Θ(n³). In practice Strassen has a larger constant factor and is less numerically stable, so real libraries only switch to it above some crossover size (the best crossover size depends heavily on the machine and the implementation — there is no single universal threshold) and fall back to the naive algorithm, or even hybrid schemes, below it.

Naive: Θ(n³). Recursive-8-multiplications: still Θ(n³) (branching factor unchanged). Strassen's 7 multiplications: Θ(n^lg7). The number of recursive multiplications per level — not how you compute their sum — determines the branching factor a, and a is what the exponent in the answer depends on.

Dart — the counters behind the table above. mulsRecursive(n) = 8^k = n³ (same as naive), mulsStrassen(n) = 7^k = n^{lg 7} with lg 7 = 2.807…; at n = 256 that is 16,777,216 vs 5,764,801 multiplications (2.91× fewer, the page animation). With the Θ(n²) additions included, T(n) = 8T(n/2) + n² solves to 2n³ − n² (33,488,896 at n = 256) and T(n) = 7T(n/2) + n² to (7^k+1 − 4^k+1)/3 (13,363,821 at n = 256).

Input size → what is feasible: pure integer recursion: Θ(lg n) calls; values stay inside Dart’s 64-bit int for n ≤ 2²⁰ (n³ ≈ 1.15·10¹⁸).

3. The substitution method

The substitution method is like checking a guessed answer to a puzzle by plugging it back in. You guess a formula for T(n) (based on experience, or on what a recursion tree suggests), then use ordinary mathematical induction to prove your guess is correct: assume it holds for all sizes smaller than n, substitute those assumed bounds into the recurrence, and check that the algebra still produces something ≤ (or ≥, or =) your guessed formula for n itself.

Two steps every time: (1) guess the form of the solution (e.g. "I bet T(n) = O(n lg n)"), then (2) prove it by induction, finding the actual constant that makes the induction go through.

Dart — the substitution method checked on numbers. tMerge evaluates T(n) = 2T(⌊n/2⌋) + n (T(1) = 1); smallestN0Guess(2, …) returns 2, i.e. the guess T(n) ≤ 2·n·lg n holds for every n from 2 up to the checked limit, while c = 1 returns null (T(2^k) = n·lg n + n always exceeds n·lg n); firstBreakOfLinearGuess shows the wrong guess cn dies at n = 4 (c = 2), 32 (c = 5), 1024 (c = 10); tSplit is Example 2, exactly 2n − 1, and inductionStepCloses(c, d, n) confirms that the strengthened guess cn − d closes the induction exactly when d ≥ 1 (d = 0 never does).

Input size → what is feasible: a check up to n = 10⁵ is 10⁵ memoised evaluations (instant); it finds constants, the induction proves them for all n.

A classic wrong "proof": guessing T(n) ≤ cn for T(n) = 2T(⌊n/2⌋) + n, substituting to get T(n) ≤ cn + n, then informally saying "cn + n = O(n), done!" That is not a valid induction step — the goal was to show T(n) ≤ cn exactly, and cn + n is not ≤ cn for any fixed positive c. You must prove your exact guessed inequality holds, not merely that the result is "still O(something)".

Sometimes the obvious guess is subtly too weak and needs a small adjustment — usually subtracting a lower-order term. For T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + 1, guessing T(n) ≤ cn gives T(n) ≤ cn + 1 after substitution — one too many. Revising the guess to T(n) ≤ cn − d (for a constant d ≥ 1) absorbs that extra +1 and makes the induction close cleanly. The final answer is still Θ(n) either way — only the proof needed adjusting, not the conclusion.

4. The recursion-tree method

A recursion tree is a literal org chart of the recursive calls: the root is the original call, its children are the subproblems it spawns, their children are the subproblems those spawn, and so on down to the base cases at the leaves. Write each node's own (non-recursive) cost inside it, then add up every level, then add up every level's total — that sum is T(n). Recursion trees are mainly used to generate a good guess, which you then confirm rigorously with the substitution method.

Try it yourself for T(n) = 2T(n/3) + cn² — the root costs cn²; each of its 2 children costs c(n/3)²; each of their 4 children costs c(n/9)²; and so on. Because each level's total shrinks by a factor of 2/9 from the level above (a decreasing geometric series), the root's own cost dominates the whole sum, up to a constant factor.

Dart — levelTotals(n) lists the level costs of T(n) = 2T(n/3) + n² for n = 3^k: level i costs (2/9)ⁱ·n² (a shrinking geometric series), the last level is the 2^k = n^{log₃ 2} leaves; treeTotal equals the direct recursion and the exact closed form T(n) = (9n² − 2·2^k)/7, which is between n² and (9/7)n². tUnbalanced evaluates T(x) = T(x/4) + T(3x/4) + x: it stays between x(log₄x − 1) and x(log_4/3x + 1) (checked at x = 100, 1000, 10000), and longestPathHeight(64) = 15.

Input size → what is feasible: the level list has lg₄ n entries; tUnbalanced visits Θ(n) nodes, so x ≤ 10⁵ is instant, x = 10⁸ is not.

A second, trickier example: T(n) = T(n/4) + T(3n/4) + cn — an unbalanced split. Every level's costs still add up to (at most) cn regardless of how unevenly the split is, but the tree's longest root-to-leaf path (always taking the bigger 3n/4 branch) has height log_{4/3}(n). Roughly cn per level, times about log_{4/3}(n) levels, gives the guess T(n) = O(n lg n) — which substitution then confirms exactly (with T(n) ≤ d·n lg n for d ≥ c/(2 − (3/4)·lg 3) ≈ 1.23c).

Recursion trees make the shape of the total cost visible: is it dominated by the root (top-heavy), spread evenly across every level, or dominated by the leaves (bottom-heavy)? That question is exactly what the master method's three cases answer in general, without redrawing a tree every time.

5. The master method

The master method is a recipe you can apply to any recurrence of the shape T(n) = aT(n/b) + f(n) (with constants a ≥ 1, b > 1) without redrawing a recursion tree from scratch every time. It works by comparing f(n) — the cost of dividing and combining — against n^(log_b a) — a number that represents how many leaves the tree ends up with. Whichever one is asymptotically bigger "wins" and determines T(n); if they're (roughly) tied, you pay an extra lg n factor.

The master theorem. For T(n) = aT(n/b) + f(n):

Case 1 — if f(n) = O(n^(log_b a − ε)) for some constant ε > 0 (f(n) is polynomially smaller), then T(n) = Θ(n^log_b a).
Case 2 — if f(n) = Θ(n^log_b a) (they match exactly), then T(n) = Θ(n^log_b a · lg n).
Case 3 — if f(n) = Ω(n^(log_b a + ε)) for some ε > 0 (f(n) is polynomially larger) and the regularity condition a·f(n/b) ≤ c·f(n) holds for some constant c < 1 and all large enough n, then T(n) = Θ(f(n)).

There are gaps between case 1 and case 2, and between case 2 and case 3, where the master method simply does not apply — for example f(n) being only a lg n factor away from n^log_b a (like T(n) = 2T(n/2) + n lg n) isn't polynomially larger, so case 3 doesn't fire, but it also isn't exactly Θ(n^log_b a), so case 2 doesn't fire either. (A generalization of case 2 — f(n)=Θ(n^log_b a lg^k n) ⇒ T(n)=Θ(n^log_b a lg^(k+1) n) for k ≥ 0 — resolves this particular kind of gap, just not via the basic theorem as literally stated.)

Try the classifier below with f(n) written as n^k · (lg n)^p — enter a, b, k, p and it will walk through exactly how the theorem classifies it:

Dart — classifyMasterMethod(a, b, k, p) for f(n) = n^k·lg^p n: it computes c = log_b a and compares k with c using a 1e-9 tolerance — k < c is Case 1, k > c Case 3 (assuming regularity), k = c Case 2 when p = 0, the generalized case 2 when p > 0, and the true gap when p < 0.

Input size → what is feasible: O(1) per call, so any a ≥ 1, b > 1, |p| ≤ 5 is instant.

Dart — tBottomUp(a, b, f, k) evaluates T(b^k) exactly and shows it settling onto the predicted shape: 4T(n/2) + n gives 2n² − n (Case 1, Θ(n²)); 2T(n/2) + n gives n lg n + n (Case 2); 2T(n/3) + n² gives T/n² → 9/7 (Case 3); 9T(n/3) + n²·lg n gives T/(n² lg² n) → 1/(2 lg 3) ≈ 0.32 (the gap case). regularityRatio computes the largest a·f(n/b)/f(n) over a range: 2/9 for 2T(n/3) + n², so c = 2/9 < 1 works; for n·lg n with a = 2, b = 3 it climbs toward 2/3 (0.64 at n = 10¹²), so c = 2/3 < 1 works (see Q15).

Input size → what is feasible: bottom-up over k levels is O(k) = O(lg n) work; k ≤ 60 stays within double range.

6. Why the master theorem is true (sketch)

The proof is really just "add up the recursion tree carefully, in general." At depth j, there are a^j nodes, each doing f(n/b^j) work; summing that over all log_b n levels, plus the Θ(n^log_b a) total cost of the n^log_b a leaves, gives the exact total T(n). What differs between the three cases is simply whether that per-level sum is a growing, constant, or shrinking geometric series as you go down the tree — and a geometric series is always dominated by either its first or its last term, which is exactly why each case reduces to a single clean formula.

Dart — the tree-sum identity as code for n = b^k, T(1) = 1: levelCosts lists a^j·f(n/b^j), leafCount = n^{log_b a} = a^k, and lemma42 = leaves + the sum of the level costs. It equals the recurrence exactly for a = 4, b = 2 and f = n, n², n³ (k = 1 … 12). shapeOf classifies the series: f = n grows downward (leaves dominate, Case 1), f = n² is flat (every level equal, Case 2), f = n³ shrinks (the root dominates, Case 3).

Input size → what is feasible: k = lg n levels, so n up to 2²⁰ is instant (values stay within 64-bit int up to n = 2²⁰ for f = n³).

Case 1: the per-level cost grows going down the tree (an increasing geometric series, because the node count aʲ outruns the shrinking f) → the n^log_b a leaves at the bottom dominate. Case 2: every level costs the same → multiply one level's cost by the number of levels (lg n). Case 3: the per-level cost shrinks going down the tree (a decreasing geometric series) → the root's own f(n) already dominates everything below it; the regularity condition a·f(n/b) ≤ c·f(n) is exactly what guarantees each level costs at most a fixed fraction c < 1 of the level above, ruling out pathological non-smooth f.

Quiz

Interview questions

Cheat sheet

Algorithm / method	Recurrence	Time	Space	When to use
Max subarray, brute force	—	Θ(n²)	O(1)	Only for tiny n or teaching
findMaximumSubarray (D&C)	T(n)=2T(n/2)+Θ(n)	Θ(n lg n)	O(lg n) stack	Illustrates the D&C pattern
Kadane's algorithm	—	Θ(n)	O(1)	The actual algorithm to use in practice/interviews
squareMatrixMultiply (naive)	—	Θ(n³)	O(n²)	Default; simplest to implement
squareMatrixMultiplyRecursive	T(n)=8T(n/2)+Θ(n²)	Θ(n³)	O(n²) + O(lg n) stack	Teaching step toward Strassen only — no real benefit
strassen	T(n)=7T(n/2)+Θ(n²)	Θ(n^lg7) ≈ Θ(n^2.807)	O(n²) + O(lg n) stack	Very large dense matrices, above the system's crossover size
Substitution method	—	—	—	Verifying a guessed bound rigorously by induction
Recursion-tree method	—	—	—	Generating a guess to then verify by substitution
Master method	T(n)=aT(n/b)+f(n)	—	—	Fast recipe classification when f(n) fits the theorem's cases