Multiplication: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Problem Description== Multiplication is one of the four elementary mathematical operations of arithmetic; with the others being addition; subtraction and division. == Bounds Chart == 1050px == Step Chart == 1050px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lo...") |
(No difference)
|
Revision as of 11:59, 10 October 2022
Problem Description
Multiplication is one of the four elementary mathematical operations of arithmetic; with the others being addition; subtraction and division.
Bounds Chart
Step Chart
Improvement Table
Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
---|---|---|
Exp/Factorial | ||
Polynomial > 3 | ||
Cubic | ||
Quadratic | Karatsuba Algorithm (1962)
[ Long Multiplication (1940)] |
|
nlogn | Harvey; Hoeven (2019) | |
Linear | ||
logn |