Difficulty: Intermediate | Prerequisites: Basic polynomial algebra, the Master Theorem (or at least how to solve recurrences of the form T(n) = aT(n/b) + O(n^c)), familiarity with divide-and-conquer.
This topic takes the Karatsuba trick for fast integer multiplication and applies it to polynomials. It is the first example in EECS 376 of a divide-and-conquer algorithm that beats the naive approach by reducing the number of recursive calls. If you have not seen Karatsuba for integers, the idea is the same: split each operand in half, and use an algebraic identity to get away with three multiplications of half-sized objects instead of four.
Naive polynomial multiplication of two degree-(n-1) polynomials takes O(n^2) coefficient multiplications. By splitting each polynomial in half and using Karatsuba's identity, you reduce to three recursive multiplications of half-sized polynomials plus O(n) additions, giving O(n^{log_2 3}) time, which is roughly O(n^{1.585}).
Polynomial multiplication
Given A(x) = a_0 + a_1 x + ... + a_{n-1} x^{n-1} and B(x) of the same form, compute the product C(x) = A(x) · B(x), which has degree at most 2n - 2. The output is the list of coefficients of C.
Divide and conquer
An algorithm design strategy that splits the problem into smaller subproblems, solves them recursively, and combines the results. Think of it as breaking a job into halves, solving each half, then merging.
Karatsuba's identity
The observation that (A_0 + A_1 x^{n/2})(B_0 + B_1 x^{n/2}) can be computed with three half-size multiplications instead of four, by computing A_0 B_0, A_1 B_1, and (A_0 + A_1)(B_0 + B_1), then recovering the cross term from these three products.
Master Theorem
A tool for solving recurrences of the form T(n) = aT(n/b) + O(n^c). For Karatsuba, a = 3, b = 2, c = 1, so T(n) = O(n^{log_2 3}).
Multiplying A(x) · B(x) directly by distributing every term of A across every term of B requires n^2 coefficient multiplications and n^2 additions. The result is O(n^2) time.
Write each polynomial as two halves:
A(x) = A_0(x) + x^{n/2} · A_1(x), where A_0 has the low-order n/2 coefficients and A_1 has the high-order n/2 coefficients.
B(x) = B_0(x) + x^{n/2} · B_1(x), defined the same way.
Then A(x) · B(x) = A_0 B_0 + x^{n/2} (A_0 B_1 + A_1 B_0) + x^n · A_1 B_1.
This looks like four half-size multiplications (A_0 B_0, A_0 B_1, A_1 B_0, A_1 B_1), which gives recurrence T(n) = 4T(n/2) + O(n) = O(n^2). No improvement yet.
Compute only three products:
P_0 = A_0 · B_0
P_2 = A_1 · B_1
P_1 = (A_0 + A_1) · (B_0 + B_1)
The cross term A_0 B_1 + A_1 B_0 = P_1 - P_0 - P_2. So:
A(x) · B(x) = P_0 + x^{n/2} · (P_1 - P_0 - P_2) + x^n · P_2
This requires three recursive multiplications of polynomials of degree at most n/2 (note that A_0 + A_1 and B_0 + B_1 each have at most n/2 coefficients), plus O(n) additions and subtractions for the combining step.
The recurrence is T(n) = 3T(n/2) + O(n).
By the Master Theorem (a = 3, b = 2, c = 1, and log_2 3 > 1), T(n) = O(n^{log_2 3}) which is approximately O(n^{1.585}).
Correctness follows from the algebraic identity:
(A_0 + A_1 x^{n/2})(B_0 + B_1 x^{n/2}) = A_0 B_0 + x^{n/2}(A_0 B_1 + A_1 B_0) + x^n A_1 B_1
and the fact that A_0 B_1 + A_1 B_0 = (A_0 + A_1)(B_0 + B_1) - A_0 B_0 - A_1 B_1. The base case (n = 1) is a single coefficient multiplication.
Karatsuba decomposition:
A · B = P_0 + x^{n/2}(P_1 - P_0 - P_2) + x^n · P_2
where P_0 = A_0 B_0, P_2 = A_1 B_1, P_1 = (A_0 + A_1)(B_0 + B_1)
Recurrence:
T(n) = 3T(n/2) + O(n)
Solution:
T(n) = O(n^{log_2 3}) which is approximately O(n^{1.585})
Karatsuba-style multiplication is used in computer algebra systems and big-number libraries (such as GMP) whenever the inputs are large enough that the overhead of recursion pays off. The same divide-and-conquer idea underlies the Fast Fourier Transform approach to polynomial multiplication, which achieves O(n log n) and powers everything from signal processing to large integer multiplication in practice.
Students sometimes believe that (A_0 + A_1)(B_0 + B_1) is the same as A_0 B_0 + A_1 B_1. It is not: the cross terms A_0 B_1 + A_1 B_0 are exactly what you extract by subtracting P_0 and P_2.
A frequent error is claiming the degree of A_0 + A_1 is n - 1. It is at most n/2 - 1, because A_0 and A_1 each have n/2 coefficients.
Some students forget the assumption that n is a power of 2. If n is not a power of 2, you pad the polynomials with zero coefficients to the next power of 2, which does not change the asymptotic running time.
Students occasionally confuse n^{log_2 3} with n^{3/2}. They are close but not the same: log_2 3 is approximately 1.585, while 3/2 = 1.5.
⚠️ Know the three products and the combining step cold. The examiner will likely ask you to write out the algorithm or fill in a missing step.
⚠️ Be able to set up and solve the recurrence T(n) = 3T(n/2) + O(n) using the Master Theorem.
⚠️ The proof of correctness is short (one algebraic identity plus induction on n). Practice writing it out cleanly.
How many half-size multiplications does the naive split require? (Four.)
How many does the Karatsuba trick reduce it to? (Three.)
True or false: log_2 3 is exactly 1.5. (False: it is approximately 1.585.)
Fill in the blank: The cross term A_0 B_1 + A_1 B_0 equals (A_0 + A_1)(B_0 + B_1) minus ___ minus ___. (A_0 B_0, A_1 B_1)
Q: Multiply A(x) = 1 + 2x and B(x) = 3 + 4x using the Karatsuba method. Verify the result.
A: A_0 = 1, A_1 = 2, B_0 = 3, B_1 = 4. P_0 = 1 · 3 = 3. P_2 = 2 · 4 = 8. P_1 = (1+2)(3+4) = 21. Cross term = 21 - 3 - 8 = 10. Result: 3 + 10x + 8x^2. Verification: (1 + 2x)(3 + 4x) = 3 + 4x + 6x + 8x^2 = 3 + 10x + 8x^2. Correct.
Q: What recurrence describes a divide-and-conquer polynomial multiplication that uses four half-size multiplications? What is its solution?
A: T(n) = 4T(n/2) + O(n). By the Master Theorem, T(n) = O(n^2), no better than the naive approach.
Q: Why do we assume n is a power of 2?
A: So the polynomials split evenly in half at every level of recursion. If n is not a power of 2, we pad with zero coefficients to the next power of 2, which at most doubles n and does not change the asymptotic running time.
Karatsuba is the gateway to sub-quadratic multiplication algorithms. The same "save one multiplication" idea appears in Strassen's matrix multiplication (seven multiplications of half-sized matrices instead of eight, giving O(n^{log_2 7})). Later in EECS 376, the FFT-based O(n log n) polynomial multiplication is covered, which dominates Karatsuba for large n. The recurrence-solving techniques here (the Master Theorem) are used throughout the course.
Karatsuba algorithm, polynomial multiplication, divide and conquer, sub-quadratic multiplication, Master Theorem, recurrence relation, n^{log_2 3}, fast multiplication, FFT polynomial multiplication, Strassen, EECS 376, algorithm design