Divide and conquer

Split into smaller instances of the same problem, recurse, combine. The paradigm behind merge sort, quicksort, binary search.

The three steps + the recurrence

• Divide into subproblems of size n/b
• Conquer them recursively
• Combine their answers with f(n) work
• Cost: T(n) = a·T(n/b) + f(n) → read by the Master Theorem

Karatsuba: 3 multiplies, not 4

• Multiply n-digit numbers: split each into high/low halves
• Naive: 4 half-size products → T(n)=4T(n/2) = O(n²)
• Trick: middle term = (hi+lo)(hi+lo) − hi·hi − lo·lo → only 3 products
• T(n)=3T(n/2)+O(n) = O(n^log₂3) = O(n^1.585)

Watch the recursion tree

8-digit multiply: 1 → 3 → 9 → 27 subproblems. Work per level 8, 12, 18, 27. Work GROWS toward the leaves → leaves dominate → n^1.585 (3 branches, not 4).

Subquadratic wins at scale

Log-log slope = exponent: schoolbook ~2, Karatsuba ~1.585. 512 digits → 2.3× faster (gap widens).

Takeaway

The COMBINE step sets the exponent, not how you split. Overlapping subproblems? Divide-and-conquer re-solves them → that's DP's job. Next: greedy — locally best choices that reach a global optimum.