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