Algorithms
Divide and Conquer (Advanced)
Difficulty: Advanced
Multiplying two n-bit integers the way you learned in school takes O(n^2) digit operations. In 1960, Karatsuba showed that the same product can be computed with three recursive multiplications instead of four, dropping the cost to...
Divide and Conquer (Advanced)
Multiplying two n-bit integers the way you learned in school takes O(n^2) digit operations. In 1960, Karatsuba showed that the same product can be computed with three recursive multiplications instead of four, dropping the cost to O(n^1.585). A few years later Strassen pulled the same trick on matrix multiplication, replacing eight recursive multiplications with seven and breaking the O(n^3) barrier for the first time. Both algorithms are pure divide-and-conquer with cleverly engineered combine steps, and they remain the gateway to a deeper view of D&C as algebraic restructuring.
Divide and Conquer (Advanced) walks through that view. You will derive Karatsuba multiplication and apply the Master Theorem to its T(n) = 3T(n/2) + O(n) recurrence. You will work through Strassen's seven-multiplication identity for 2 x 2 blocks and discuss when its higher constant factor pays off in practice. You will solve closest-pair-of-points in 2D in O(n log n) via the strip optimization in the combine step, and look at convex-hull computation through a divide-and-conquer lens.
In Divide and Conquer (Intro), you applied the Master Theorem to merge sort and quick sort. Recursion Fundamentals gave you the call-stack model these algorithms still inhabit. This lesson keeps the recurrence framework but engineers cleverer combine steps.
Next, Mathematical Algorithms turns to number-theoretic computation.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement Karatsuba multiplication and explain why it achieves O(n^1.585) via the Master Theorem.
Describe Strassen's matrix multiplication and explain how reducing 8 multiplications to 7 improves complexity.
Implement the closest pair of points algorithm in 2D with the strip optimization.
Apply the Master Theorem to analyze recurrences of the form T(n) = aT(n/b) + O(n^d).
Compare advanced D&C algorithms with their brute-force counterparts and identify when D&C overhead is worth it.
Why This Matters
01
Karatsuba multiplication demonstrates that the 'obvious' O(n^2) algorithm for multiplying large numbers is not optimal — a single algebraic trick reduces three subproblems to the work of two, achieving O(n^1.585).
02
Strassen's matrix multiplication is a landmark result in algorithm design: by reducing 8 recursive multiplications to 7, it achieves O(n^2.807) and proves that matrix multiplication can be faster than O(n^3).
03
The closest pair of points algorithm is a masterclass in D&C design: the divide step is easy, but the combine step requires a subtle geometric argument to stay O(n log n).
04
Understanding these algorithms deepens your intuition for the Master Theorem and helps you recognize when D&C can improve upon brute-force approaches in interviews and competitions.
Key Terms
6 terms you'll encounter in this lesson
Karatsuba Multiplication
A divide-and-conquer algorithm for multiplying large numbers that uses 3 multiplications of half-sized numbers instead of 4, achieving O(n^1.585) instead of O(n^2).
Strassen's Algorithm
A matrix multiplication algorithm that multiplies two n x n matrices using 7 recursive multiplications of (n/2) x (n/2) matrices instead of 8, achieving O(n^2.807).
Closest Pair of Points
The problem of finding two points with minimum Euclidean distance among n points. The D&C solution runs in O(n log n) by splitting points by x-coordinate and cleverly merging with a strip optimization.
Master Theorem
A formula for solving recurrences of the form T(n) = aT(n/b) + O(n^d). Depending on the relationship between log_b(a) and d, the solution is O(n^d), O(n^d log n), or O(n^(log_b(a))).
Strip Optimization
In the closest pair algorithm, after finding the minimum distance delta in each half, only points within delta of the dividing line need cross-half comparison. Each point compares to at most 7 others in the strip.
Crossover Point
The input size below which a simpler (but asymptotically slower) algorithm is faster due to lower constant factors. Advanced D&C algorithms typically switch to brute force for small inputs.
Heads Up
Common misconceptions to watch out for
"Strassen's algorithm is always faster than standard matrix multiplication"
Strassen's has higher constant factors and numerical instability. For matrices smaller than roughly 32x32 to 128x128 (depending on hardware), standard O(n^3) multiplication is faster. Practical implementations use Strassen for large matrices and switch to standard multiplication below a crossover point.
"The closest pair strip can contain O(n) points, making the combine step O(n^2)"
While the strip can indeed contain O(n) points, each point only needs to be compared with at most 7 others (those within delta distance in sorted y-order). This keeps the combine step at O(n), not O(n^2).
"Karatsuba just splits the number in half and multiplies recursively"
Simple splitting would still give 4 recursive multiplications (O(n^2)). Karatsuba's key insight is computing (a+b)(c+d) to derive the cross term ac + bd, reducing from 4 multiplications to 3.