Divide and Conquer/Polynomial Multiplication: Difference between revisions
From charlesreid1
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
* Addition | * Addition | ||
* Multiplication | * Multiplication | ||
{| class="wikitable" cellpadding="100" width="66%" | |||
!colspan="4"|Big-O Complexity of Polynomial Operations | |||
|- | |||
|<br /><br /> | |||
Operation | |||
|<br /><br /> | |||
Coefficient Representation | |||
|<br /><br /> | |||
Roots Representation | |||
|<br /><br /> | |||
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) | |||
|} | |||
Revision as of 23:04, 15 August 2017
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) |