Divide and Conquer/Polynomial Multiplication: Difference between revisions
From charlesreid1
No edit summary |
|||
| Line 34: | Line 34: | ||
|O(n) | |O(n) | ||
|style="background-color: #700;"| | |style="background-color: #700;"| | ||
O(n^2) | |||
|- | |- | ||
| Line 40: | Line 40: | ||
|O(n) | |O(n) | ||
|style="background-color: #700;"| | |style="background-color: #700;"| | ||
Infinite time | |||
|O(n) | |O(n) | ||
| Line 46: | Line 46: | ||
|Multiplication | |Multiplication | ||
|style="background-color: #700;"| | |style="background-color: #700;"| | ||
O(n^2) | |||
|O(n) | |O(n) | ||
|O(n) | |O(n) | ||
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) |