Divide and Conquer: Reading the Cost off the Shape of the Recursion

Binary search. Merge sort. Quicksort. Line up the last three algorithms this course taught you and they are the same move in three costumes. Binary search split the array at the middle and threw half away. Merge sort split at the middle and trusted both halves. Quicksort split around a pivot and recursed on the sides. Split, recurse, put the answer together: you've been using one of the most famous ideas in computer science for three lessons without being told its name.

The name is divide and conquer, and naming it is the smaller half of this lesson. The bigger half is the promise lesson 10 closed on: log n levels and n work per level showed up twice, in two different algorithms, and the arithmetic came out identical both times. That was not a coincidence. There is a way to read the cost of any algorithm shaped like this straight off the shape of its recursion, no algebra required, and that skill, not the name, is what you'll carry out of this page.

The template

The paradigm has three beats:

function solve(problem):
    if problem is small enough:            # base case
        return the direct answer
    pieces = divide(problem)               # divide: split the input
    answers = solve(each piece)            # conquer: the leap of faith from lesson 9
    return combine(answers)                # combine: assemble the whole answer

Divide: split the input into smaller pieces, usually halves. Conquer: solve each piece with a recursive call, written as if it already works (lesson 9's leap of faith). Combine: assemble the pieces' answers into the answer for the whole.

Now hold each known algorithm up against the template, because the differences are where the insight lives:

Merge sort is the textbook fit: cheap split, recurse on both halves, do the real work after, in the combine. Quicksort plays the beats in a different order: the partition does the real work first, arranging small elements left and big elements right, so that when the two sides come back sorted there is nothing left to combine. The combine was prepaid. And binary search is the degenerate case, in the best way: it divides at the middle, but one comparison proves the answer can't be in one of the halves, so it conquers one half and abandons the other. No combine at all.

Recurse on both halves and pay a combine, or recurse on one and pay almost nothing. Keep that distinction in view; it's about to become the entire cost story.

Pricing the tree: levels times work per level

Here is the trick, and it fits in one sentence: draw the recursion tree, and the total cost is the work per level, times the number of levels. Lesson 9 taught you to see the tree; this section teaches you to bill it. Three shapes cover nearly everything.

One branch: the chain

Binary search does constant work per call (one comparison), then recurses on half. The "tree" is a chain: n, then n/2, then n/4, down to 1. Number of levels: how many times you can halve n, which is log n (about 20 for a million, 30 for a billion, per lesson 1). Work per level: constant. Constant work times log n levels is O(log n), the price lesson 8 derived by counting halvings, now read straight off the shape. When only the levels cost anything, the levels alone set the price.

Two branches, flat tree

Merge sort recurses on both halves with a linear combine, and its tree is the full picture from lesson 10: n at the root, two halves below, four quarters below that, down to single elements. Bill it level by level. The root's merge moves n elements: n work. The next level runs two merges of n/2 each: n again. Then four merges of n/4: still n. Every level moves the same n elements, so the tree is flat, and a flat tree bills n work per level times log n levels: O(n log n). No summations, no induction, five seconds of looking.

Quicksort with good pivots is the same picture from the other direction: each level's partitions touch n elements total, log n levels deep. Two branches plus a linear combine (or a linear divide; the tree doesn't care when the work happens) always produces a flat tree, and a flat tree always bills n log n. Lesson 1's "halve-and-recombine" rung is not a formula to memorize. It's a shape you can recognize on sight.

The dominant level

Not every tree is flat. Suppose splitting is cheap but combining costs n². The root bills n². The next level bills two combines of (n/2)², which is n²/2. The next, n²/4. Each level costs half the one above, and lesson 1's doubling sum (run in reverse) says the whole tower sums to at most twice the root. The root dominates: total O(n²), and the recursion underneath was noise.

Flip it: if work per level grows as you descend (more branches than the shrinking makes up for), the leaves dominate, and the total is essentially the number of leaves. Karatsuba's multiplication, later in this lesson, is exactly this case.

So every divide and conquer tree tells one of three stories:

There is a formula that mechanizes this three-way split. It's called the master theorem, and it's honest reference material: look it up when you meet a recurrence in the wild, plug in how many branches, how much shrink, how much combine. But it is exactly these three stories with the cases labeled, and for this course, levels times work per level is the tool. It prices everything in part 1 and most of what you'll ever meet.

A fresh problem: maximum subarray

The paradigm shouldn't only relabel old wins, so here's a new problem. Given an array of numbers, some negative, find the contiguous stretch with the largest sum:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Somewhere in there hides the best run. Brute force tries every stretch: every start, every end, sum each one. That's lesson 1's quadratic triangle again, dead at scale.

Think like the last three lessons instead. Split the array at the middle. The best stretch now lives in exactly one of three places:

1. Entirely in the left half: the same problem, smaller. Recursive call.
2. Entirely in the right half: recursive call.
3. Crossing the middle, one foot on each side: the only new work. The combine.

The crossing case looks hard until you notice what crossing means: the stretch touches the middle boundary, so it must be a best suffix of the left half glued to a best prefix of the right half, and each side is one scan. Split our array after index 4, so the left half is [-2, 1, -3, 4, -1] and the right half is [2, 1, -5, 4]. Walk left from the boundary, keeping a running sum and the best ever seen:

Best suffix: 3, the stretch [4, -1]. Now walk right from the boundary:

Best prefix: 3, the stretch [2, 1]. Glue them: 3 + 3 = 6, the crossing stretch [4, -1, 2, 1]. The recursion (trusted, per lesson 9) reports the best stretch inside the left half is 4 and inside the right half is 4. The answer is the max of the three zones: 6.

Now price it without running it: two recursive calls on halves plus a linear combine (the two scans together touch each element once). You have seen this tree. It's merge sort's tree. Flat. O(n log n), read off the shape.

The punchline: Kadane's one pass

Divide and conquer just turned a quadratic problem into n log n, and for a while that was the best anyone knew. This problem has a history: it comes from pattern detection in digitized images (the statistician Ulf Grenander posed it as a one-dimensional warm-up for a maximum-likelihood image problem), and Jon Bentley carried it through the industry as one of his Programming Pearls. Then Jay Kadane, a statistician at Carnegie Mellon, heard the problem in a seminar and sketched, reportedly in under a minute, a plain loop that beats the recursion.

One pass, two numbers: the best stretch ending exactly here, and the best stretch seen anywhere. At each element, the best stretch ending here either extends the previous one or starts fresh at this element, whichever is larger:

Same answer, 6. O(n) time, O(1) space, no recursion at all. This is Kadane's algorithm, and the full account of why "extend or start fresh" is always safe belongs to dynamic programming, which the patterns course owns.

Sit with what just happened, because it's the meta-lesson of the whole page. The divide and conquer solution was not wasted: it's the rung on the ladder that proved the quadratic was beatable, and the crossing-sum insight (running sums from a boundary) is quietly load-bearing inside Kadane's loop. But the paradigm is a design tool, not a guarantee of optimality. Sometimes the recursive solution is the stepping stone, and a one-pass loop is standing at the top.

The week Karatsuba broke a conjecture

Now the story that made this paradigm famous, because it didn't just speed up a function; it killed a conjecture.

Moscow, 1960. Andrey Kolmogorov, one of the great mathematicians of the century, runs a seminar and states a belief: multiplying two n-digit numbers the schoolbook way costs n² digit-operations, and n², he conjectures, is optimal. In the audience sits a 23-year-old student, Anatoly Karatsuba. Within a week he has a counterexample.

The mechanics, kept light. Split each n-digit number into a high half and a low half. The schoolbook product needs four multiplications of those halves (high×high, high×low, low×high, low×low). Karatsuba found an algebra trick that recovers the same answer from three half-size multiplications plus a few additions, because the two middle terms can be extracted from (high+low)×(high+low) once the outer two products are known. Three branches instead of four, on halves: a bottom-heavy tree, but a thinner one. The leaves dominate, and counting them gives about n^1.58 instead of n². The conjecture was dead, and Kolmogorov himself wrote the result up for publication.

The descendants of that week are working for you right now. CPython switches integer multiplication to Karatsuba once your numbers pass about 70 digits. GMP, the big-number library underneath most scientific and cryptographic computing, climbs through Karatsuba and its successors as numbers grow. The bignum code multiplying 2,048-bit numbers to open a TLS connection carries the same lineage. (Strassen later pulled the same three-instead-of-four trick on matrix multiplication; that thread belongs to a deeper course.)

Free parallelism

One more thing the shape buys. Merge sort's two halves share nothing: different memory, no coordination, no order between them. Independent subproblems can run on different cores, then four, then eight, and divide and conquer is the reason so much work parallelizes naturally. This is not theoretical: Java's ForkJoinPool is a thread pool designed explicitly around fork-the-halves/join-the-results, Rust's rayon exposes join(left, right) as its core primitive, and C++ ships parallel std::sort via execution policies.

Stretch the idea to its limit and you get MapReduce, the 2004 Google framework (and the Hadoop/Spark lineage it spawned): divide a job across thousands of machines, conquer the pieces independently, combine the results in a reduce step. Datacenter-scale computing runs on the same three beats as merge sort.

When divide and conquer loses

The honest list, because a tool is only trustworthy once you know its failure modes.

The subproblems overlap. The pricing trick assumes the tree's nodes are distinct work. Lesson 9's Fibonacci recursed on overlapping inputs, recomputed the same answers exponentially many times, and produced the O(2ⁿ) tree. Splitting only pays when the pieces are independent; when they overlap, the fix is remembering answers instead of recomputing them, which is dynamic programming, and dsa-patterns gives it the full treatment.

The combine costs too much. A top-heavy tree bills its root, so if combining costs as much as solving from scratch, the recursion bought nothing. Splitting an unsorted array in half is free, but if your "combine" has to re-examine every pair across the boundary, you've rebuilt the quadratic.

The problem doesn't actually shrink geometrically. Lesson 10's quicksort catastrophe, reread through this lesson's lens: on sorted input with a bad pivot, "divide" produced pieces of size n-1 and 0. Shrink-by-one means n levels, not log n, and the flat-tree bill becomes n × n. If the pieces aren't a constant fraction smaller, you don't have divide and conquer. You have a loop wearing its costume.

The real code

The videos stay in pseudocode; here is maximum subarray, divide and conquer, in the three languages this course carries, with the punchline after.

function maxCrossing(items: number[], lo: number, mid: number, hi: number): number {
  let sum = 0
  let bestLeft = -Infinity // best suffix of the left half, ending at mid
  for (let i = mid; i >= lo; i--) {
    sum += items[i]
    bestLeft = Math.max(bestLeft, sum)
  }
  sum = 0
  let bestRight = -Infinity // best prefix of the right half, from mid+1
  for (let j = mid + 1; j <= hi; j++) {
    sum += items[j]
    bestRight = Math.max(bestRight, sum)
  }
  return bestLeft + bestRight
}
 
function maxSubarray(items: number[], lo = 0, hi = items.length - 1): number {
  if (lo === hi) return items[lo] // base case: one element is its own best stretch
  const mid = lo + Math.floor((hi - lo) / 2)
  const left = maxSubarray(items, lo, mid) // the leap
  const right = maxSubarray(items, mid + 1, hi) // of faith
  return Math.max(left, right, maxCrossing(items, lo, mid, hi))
}

func maxCrossing(items []int, lo, mid, hi int) int {
	sum, bestLeft := 0, math.MinInt
	for i := mid; i >= lo; i-- {
		sum += items[i]
		bestLeft = max(bestLeft, sum)
	}
	sum = 0
	bestRight := math.MinInt
	for j := mid + 1; j <= hi; j++ {
		sum += items[j]
		bestRight = max(bestRight, sum)
	}
	return bestLeft + bestRight
}
 
func maxSubarray(items []int, lo, hi int) int {
	if lo == hi {
		return items[lo]
	}
	mid := lo + (hi-lo)/2
	left := maxSubarray(items, lo, mid)
	right := maxSubarray(items, mid+1, hi)
	return max(left, right, maxCrossing(items, lo, mid, hi))
}

int max_crossing(const std::vector<int>& items, int lo, int mid, int hi) {
    int sum = 0, best_left = INT_MIN;
    for (int i = mid; i >= lo; --i) {
        sum += items[i];
        best_left = std::max(best_left, sum);
    }
    sum = 0;
    int best_right = INT_MIN;
    for (int j = mid + 1; j <= hi; ++j) {
        sum += items[j];
        best_right = std::max(best_right, sum);
    }
    return best_left + best_right;
}
 
int max_subarray(const std::vector<int>& items, int lo, int hi) {
    if (lo == hi) return items[lo];
    int mid = lo + (hi - lo) / 2;  // overflow-safe midpoint: lesson 8's famous bug
    return std::max({ max_subarray(items, lo, mid),
                      max_subarray(items, mid + 1, hi),
                      max_crossing(items, lo, mid, hi) });
}

Read the TypeScript against the lesson. maxSubarray is the template verbatim: base case, divide at mid, two trusted calls, and the combine is maxCrossing plus a three-way max. maxCrossing is the two table-scans from the walkthrough: the first loop walks outward to the left from the boundary (note i--), the second walks right, and each keeps the running-sum/best-ever pair. The two loops together touch each element in the range once: the linear combine that makes the tree flat.

The Go version is the same skeleton; math.MinInt plays the role of negative infinity (the best-so-far must start below any real sum, because an all-negative array's answer is its largest single element, not zero), and Go's built-in max happily takes all three zones at once.

The midpoint line is lo + (hi - lo) / 2 for the third lesson running, and for the same reason: Bloch's overflow bug lives in every divide step ever written. Price check on all three versions: two calls on halves, linear combine, flat tree, O(n log n) time, O(log n) stack (the friendly recursion depth from lesson 9).

And the punchline, Kadane's pass, in TypeScript (Go and C++ are the same five lines with their own max):

function maxSubarrayKadane(items: number[]): number {
  let bestHere = items[0] // best stretch ending exactly here
  let best = items[0] // best stretch anywhere so far
  for (let i = 1; i < items.length; i++) {
    bestHere = Math.max(items[i], bestHere + items[i]) // extend, or start fresh
    best = Math.max(best, bestHere)
  }
  return best
}

One pass, two variables, no recursion. The Math.max(items[i], bestHere + items[i]) line is the entire algorithm: extend the running stretch or abandon it and start here. When the running sum has gone negative, starting fresh always wins, which is the crossing-scan insight wearing a loop.

Where this shows up in production

• Every sort you call. Lesson 10's library hybrids (Timsort, introsort, pdqsort) are divide and conquer engines with engineering wrapped around the template, and external sorting (sort runs, merge streams) is the combine step running against disks.
• Parallel runtimes. Java's ForkJoinPool, Rust's rayon, .NET's task parallelism: the APIs are shaped like fork-halves-then-join because independent subproblems are what cores can actually share.
• MapReduce and its descendants. Hadoop and Spark jobs are divide (shard the data), conquer (map), combine (reduce), at warehouse scale.
• Big-integer arithmetic. CPython's int multiply goes Karatsuba past ~70 digits; GMP and the bignum cores inside TLS libraries climb the same ladder for cryptographic sizes.

Closing the module, and what's next

This closes the module. Three lessons ago recursion was magic; now the machinery is open (a call is a frame, depth is memory), writing a recursive solution is two decisions (a base case and one trusted step), and pricing one is a glance at the tree (levels times work per level). You can write the recursive sorts and bill them on sight. That was the module's whole promise, and it's kept.

Next, a new module, and a structure this course has owed you since day one. Lesson 1 asked you to file something away: a structure whose average case is O(1), whose worst case is O(n), and whose entire engineering story is making that worst case so rare you can price it at the average. Time to take it off the file. Hash tables: how any key becomes an array index, what happens when two keys collide, and why every hash table you've ever used occasionally stops to rebuild itself.