Divide and Conquer/Polynomial Multiplication
From charlesreid1
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) |