Divide & Conquer Splits

Foundations

In the first lesson, each call made one smaller call, one step closer to the base case, so n steps meant a stack n frames deep. Now, what if each call cuts the problem in half instead?

Divide and conquer splits the input into halves, solves each half with the same function, and combines the two answers. The base case is a piece small enough to answer directly, usually one element. Halving reaches that size after about log₂ n levels, so the stack is only O(log n) deep. When both halves are the same subproblem, solve it once and reuse the answer.

Find the largest value of nums = [7, 1, 5, 3, 6] by halves: best([7, 1, 5, 3, 6]) splits into best([7, 1]) and best([5, 3, 6]), which split again down to single elements. Each pair combines with max: the left half returns 7, the right half returns 6, and max(7, 6) = 7. The stack is never more than 4 calls deep.

Case Scenario

Pow(x, n) asks for x raised to the power n, where n can be near 2³¹ or negative. The split is on the exponent: x^n = x^(n // 2) * x^(n // 2), times one more x when n is odd. Both halves are the same power, so one call serves both. For x = 2.0 and n = 10, the calls go 10, 5, 2, 1, 0, and the answer is 1024.0.

The direct approach multiplies x by itself n times: O(n) multiplications, ten here, but over two billion when n is near 2³¹. It never notices that the second half of those multiplications repeats the first half exactly.