Difficulty: Intermediate to Advanced | Prerequisites: Big-O notation, basic recurrences, familiarity with the integer Karatsuba algorithm, the Master Theorem.
Divide-and-conquer algorithms split a problem into smaller subproblems, solve them recursively, and combine the results. The Karatsuba algorithm for integer multiplication is the classic example: it reduces four multiplications to three by cleverly reusing partial products. This homework extends that idea to polynomial multiplication. The second half covers solving recurrence relations, which is how you determine the running time of divide-and-conquer algorithms. These recurrences appear constantly in algorithm analysis, so fluency with them is essential for the rest of the course.
Karatsuba's trick works for polynomials too: split each polynomial in half, compute three recursive multiplications instead of four, and combine. The recurrence T(n) = 3T(n/2) + O(n) gives O(n^{log_2 3}) time, roughly O(n^{1.585}). Solving recurrences with the Master Theorem or by substitution and expansion is how you get these bounds.
Karatsuba algorithm
A divide-and-conquer multiplication algorithm that reduces the number of recursive multiplications from four to three by computing one extra addition and subtraction. In simple terms, it is a clever shortcut for multiplying large numbers (or polynomials) faster than the naive method.
Divide and conquer
An algorithm design strategy that breaks a problem into smaller subproblems of the same type, solves them recursively, and combines the results. Think of it as "split the work, solve each piece, then put it back together."
Recurrence relation
An equation that defines a function T(n) in terms of T on smaller inputs, such as T(n) = 3T(n/2) + O(n). In simple terms, it describes the running time of a recursive algorithm by saying "the cost is the cost of the smaller calls plus the cost of combining."
Master Theorem
A formula that gives a closed-form asymptotic bound for recurrences of the form T(n) = aT(n/b) + O(n^d). Think of it as a lookup table: plug in a, b, d and read off whether the recursion, the combine step, or both dominate.
Polynomial multiplication
Computing the product of two polynomials A(x) and B(x), producing a new polynomial whose coefficients are the convolution of the original coefficients. The naive method is O(n^2); Karatsuba brings it to O(n^{log_2 3}).
Given polynomials A(x) and B(x) of degree at most n-1 (with n a power of 2), split each into high and low halves:
A(x) = p(x) \cdot x^{n/2} + q(x), \quad B(x) = r(x) \cdot x^{n/2} + s(x)Here p(x) and r(x) hold the upper n/2 coefficients (with x^{n/2} factored out), and q(x) and s(x) hold the lower n/2 coefficients. All four are polynomials of degree at most n/2 - 1.
Expanding directly:
A(x) \cdot B(x) = p(x)r(x) \cdot x^n + (p(x)s(x) + q(x)r(x)) \cdot x^{n/2} + q(x)s(x)This requires four recursive multiplications: pr, ps, qr, qs. That gives T(n) = 4T(n/2) + O(n) = O(n^2), no better than naive.
The key identity:
p(x)s(x) + q(x)r(x) = (p(x) + q(x))(r(x) + s(x)) - p(x)r(x) - q(x)s(x)Compute only three products:
M1(x) = p(x) * r(x)
M2(x) = q(x) * s(x)
M3(x) = (p(x) + q(x)) * (r(x) + s(x))
Then:
A(x) \cdot B(x) = M_1(x) \cdot x^n + (M_3(x) - M_1(x) - M_2(x)) \cdot x^{n/2} + M_2(x)The additions and shifts are O(n). The three recursive calls are on polynomials of degree n/2. So:
T(n) = 3T(n/2) + O(n)By the Master Theorem (a = 3, b = 2, d = 1, and log_2 3 > 1), this is Case 3:
T(n) = O(n^{\log_2 3}) \approx O(n^{1.585})When a = 1, the recurrence is T(n) = T(n - b) + n. Unrolling:
T(n) = \sum_{i=0}^{n/b} (n - ib) = n^2 - \frac{bn(n+1)}{2} = O(n^2)Each recursive call reduces n by b, so there are about n/b levels, and each level adds roughly n work. The sum is quadratic.
When a > 1, the number of subproblems grows exponentially. Use the substitution S(2^n) := T(n), which gives T(log_2 n) = S(n).
Substituting into the recurrence:
S(n) = a \cdot S\left(\frac{n}{2^b}\right) + \log_2 nThis is nearly in Master Theorem form. Since log_2 n grows slower than any polynomial n^epsilon, the recursive term dominates (Case 3 of the Master Theorem):
S(n) = O\left(n^{\log_{2^b} a}\right)Converting back to T(n):
T(n) = S(2^n) = O\left(2^{n \cdot \log_{2^b} a}\right) = O\left(2^{\frac{\log a}{b} \cdot n}\right)So T(n) grows exponentially when a > 1. The base of the exponential is 2^{(log a)/b}.
This recurrence resembles the a > 1 case above but with a floor function and log n instead of n. The key insight is that at powers of 2^c, this recurrence matches S(n) from the previous section exactly (with a = 2c and b = c).
When n = 2^{ck}, the recurrence simplifies cleanly and by the same Master Theorem argument:
M(2^{ck}) = O\left((2^{ck})^{\frac{\log 2c}{c}}\right)For n that is not a power of 2^c, use induction to show M(n) <= M(2^{c * ceil(log n / c)}). The idea is that M is non-decreasing (the floor can only reduce the argument, so larger n gives larger M), so you can bound M(n) by M at the next power of 2^c above it.
M(n) = O\left(n^{\frac{\log 2c}{c}}\right)This proof is noted as "quite difficult and outside the scope of this course" in the solutions, so the main takeaway is the result and the intuition that floor recurrences behave like their clean counterparts at the right input values.
Karatsuba polynomial recurrence:
T(n) = 3T(n/2) + O(n) \implies T(n) = O(n^{\log_2 3})Master Theorem (standard form):
For T(n) = aT(n/b) + O(n^d):
Case 1: If a < b^d, then T(n) = O(n^d).
Case 2: If a = b^d, then T(n) = O(n^d log n).
Case 3: If a > b^d, then T(n) = O(n^{log_b a}).
Linear recurrence (a = 1):
T(n) = T(n-b) + n \implies T(n) = O(n^2)Exponential recurrence (a > 1):
T(n) = a \cdot T(n-b) + n \implies T(n) = O\left(2^{\frac{\log a}{b} \cdot n}\right)Floor recurrence result:
M(n) = 2c \cdot M\left(\lfloor n/2^c \rfloor\right) + \log n \implies M(n) = O\left(n^{\frac{\log 2c}{c}}\right)Karatsuba identity (the algebraic trick):
ps + qr = (p+q)(r+s) - pr - qsKaratsuba multiplication is used in practice for large-number arithmetic libraries (GMP, Python's built-in big integers). For very large numbers, even faster algorithms exist (Toom-Cook, FFT-based), but Karatsuba is the simplest sub-quadratic method. Polynomial multiplication is central to signal processing (convolution), error-correcting codes, and computer algebra systems.
Students sometimes think the Karatsuba trick gives O(n log n) time. It does not. It gives O(n^{log_2 3}), which is approximately O(n^{1.585}). O(n log n) polynomial multiplication requires FFT-based methods.
A common error when solving T(n) = aT(n - b) + n with a > 1 is to treat it like T(n) = aT(n/b) + n. The subtraction form (n - b) gives exponential growth, while the division form (n/b) gives polynomial growth. These are fundamentally different.
Students often forget that the Karatsuba identity requires computing p + q and r + s first, and these sums may have degree n/2 (not n/2 - 1), so the recursive call on M3 is on slightly larger polynomials. The asymptotic analysis still works, but be careful in implementation.
When applying the Master Theorem, students sometimes mix up which case they are in. Remember: compare a to b^d. If a > b^d, the recursion dominates. If a < b^d, the combine step dominates. If equal, you get an extra log factor.
⚠️ Know the Karatsuba identity and be able to derive the three-multiplication algorithm from it.
⚠️ Be able to state and apply all three cases of the Master Theorem.
⚠️ The substitution S(2^n) = T(n) for converting subtraction recurrences to division recurrences is a standard trick. Expect to use it.
⚠️ Know the difference between T(n) = aT(n - b) + f(n) (exponential when a > 1) and T(n) = aT(n/b) + f(n) (polynomial, handled by Master Theorem).
True or false: Karatsuba polynomial multiplication runs in O(n log n) time. False (it runs in O(n^{log_2 3})).
Fill in the blank: The Karatsuba trick reduces ___ recursive multiplications to ___. Four to three.
True or false: T(n) = 2T(n - 1) + n grows polynomially. False (it grows exponentially, O(2^n)).
Fill in the blank: In the Master Theorem for T(n) = aT(n/b) + O(n^d), if a > b^d, then T(n) = O(___). n^{log_b a}.
True or false: The substitution S(2^n) = T(n) converts a subtraction recurrence into a division recurrence. True.
Q: Write the Karatsuba identity for polynomial products. Why does it save a multiplication?
A: p(x)s(x) + q(x)r(x) = (p(x)+q(x))(r(x)+s(x)) - p(x)r(x) - q(x)s(x). Since pr and qs are already computed for the x^n and constant terms, computing (p+q)(r+s) is the only new multiplication needed. Total: three multiplications instead of four.
Q: Solve T(n) = T(n - 3) + n for T(n) when T is constant for n <= 3.
A: Unrolling gives T(n) = sum from i=0 to n/3 of (n - 3i) = O(n^2). There are about n/3 levels, each contributing roughly n, so the sum is quadratic.
Q: Solve T(n) = 4T(n - 2) + n. What is the asymptotic growth?
A: Use the substitution S(2^n) = T(n). Then S(n) = 4 * S(n/4) + log n. By the Master Theorem with a = 4, b = 4, the log n term is dominated, giving S(n) = O(n^{log_4 4}) = O(n). Converting back: T(n) = S(2^n) = O(2^n). More precisely, T(n) = O(2^{(log 4 / 2) * n}) = O(2^n).
Q: What are the three cases of the Master Theorem?
A: For T(n) = aT(n/b) + O(n^d): Case 1 (a < b^d): T(n) = O(n^d). Case 2 (a = b^d): T(n) = O(n^d log n). Case 3 (a > b^d): T(n) = O(n^{log_b a}).
(This section intentionally left blank; see Practice Q&A above.)
Karatsuba is the first example of a sub-quadratic multiplication algorithm in EECS 376. It leads to FFT-based polynomial multiplication (O(n log n)), which appears in advanced algorithms courses. Recurrence relations are the primary tool for analysing any divide-and-conquer algorithm, from merge sort (T(n) = 2T(n/2) + O(n)) to Strassen's matrix multiplication (T(n) = 7T(n/2) + O(n^2)). The subtraction-form recurrence T(n) = aT(n-b) + f(n) reappears in dynamic programming analysis.
Karatsuba algorithm, polynomial multiplication, divide and conquer, recurrence relation, Master Theorem, asymptotic analysis, big-O, O(n^{log_2 3}), subtraction recurrence, exponential recurrence, substitution method, EECS 376 Homework 1, University of Michigan, Foundations of Computer Science, Toom-Cook, FFT multiplication, Strassen