Divide and Conquer/Polynomial Multiplication

Overview

Start with overview of what we've covered so far:

Polynomials are useful mathematical objects.

We can represent them in three ways:

• Coefficients vector
• Roots vector
• Samples vector

We also have three different algorithms/operations we wish to define:

• Evaluation
• Addition
• Multiplication

Making a table of what operations take what amounts of time, we get:

Big-O Complexity of Polynomial Operations
Operation	Coefficient Representation	Roots Representation	Samples Representation
Evaluation:	O(n)	O(n)	O(n^2)
Addition:	O(n)	Infinite time	O(n)
Multiplication	O(n^2)	O(n)	O(n)

The Goal

Given that the roots representation contains an infinite cell, we'll ignore it in the search for practical solutions to our problem.

Our goal is to implement a linear time algorithm for each operation. The table above shows we are almost there, but the last multiplication row causes some issues.

Specifically, we would like to be able to get the best of both worlds. However, converting from a coefficients representation to a samples representation, or vice-versa, takes quadratic time (because you have N samples, and your overall algorithm performs N operations on each sample, so you end up with a quadratic algorithm.)

Here, we will cover a way to go from a samples representation to a coefficients representation, or vice-versa, in O(N log N) time.