Karatsuba Multiplication: Difference between revisions
Jump to navigation
Jump to search
[Next]
(→TODO) |
|||
| Line 9: | Line 9: | ||
* Karatsuba: explain the key idea – apply the master theorem to demonstrate that the complexity is still O(n2). The key insight for Karatsuba algorithm is the Gauss’ trick to reduce four sub-parts recursive multiplications to 3, and the complexity is ? | * Karatsuba: explain the key idea – apply the master theorem to demonstrate that the complexity is still O(n2). The key insight for Karatsuba algorithm is the Gauss’ trick to reduce four sub-parts recursive multiplications to 3, and the complexity is ? | ||
</font> | </font> | ||
Link to [[Matrix_Multiplication#Strassen|Strassen]]. | |||
=Overview= | =Overview= | ||
Revision as of 20:04, 20 September 2021
Internal
TODO
- problem statement
- naïve solution
- Gauss trick
- complexity
- Karatsuba: explain the key idea – apply the master theorem to demonstrate that the complexity is still O(n2). The key insight for Karatsuba algorithm is the Gauss’ trick to reduce four sub-parts recursive multiplications to 3, and the complexity is ?
Link to Strassen.
Overview
Apply the Gauss' trick and end up with three recursive calls instead of four. This yields a O(n*logn) complexity. It if was four, the recursive complexity it would have been O(n2).
TODO