Divide and Conquer/Polynomial Multiplication: Difference between revisions
From charlesreid1
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
==Overview== | |||
Start with overview of what we've covered so far: | Start with overview of what we've covered so far: | ||
| Line 12: | Line 14: | ||
* Addition | * Addition | ||
* Multiplication | * Multiplication | ||
Making a table of what operations take what amounts of time, we get: | |||
{| class="wikitable" cellpadding="100" width="66%" | {| class="wikitable" cellpadding="100" width="66%" | ||
| Line 29: | Line 33: | ||
|O(n) | |O(n) | ||
|O(n) | |O(n) | ||
|style="background-color: #700;"| | |||
|O(n^2) | |O(n^2) | ||
| Line 34: | Line 39: | ||
|Addition: | |Addition: | ||
|O(n) | |O(n) | ||
|style="background-color: #700;"| | |||
|Infinite time | |Infinite time | ||
|O(n) | |O(n) | ||
| Line 39: | Line 45: | ||
|- | |- | ||
|Multiplication | |Multiplication | ||
|style="background-color: #700;"| | |||
|O(n^2) | |O(n^2) | ||
|O(n) | |O(n) | ||
| Line 44: | Line 51: | ||
|} | |} | ||
[[Category:Math]] | [[Category:Math]] | ||
[[Category:Polynomials]] | [[Category:Polynomials]] | ||
Revision as of 23:14, 15 August 2017
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) | |