Karatsuba Multiplication: Difference between revisions
Jump to navigation
Jump to search
[Next]
| Line 2: | Line 2: | ||
=Overview= | =Overview= | ||
Apply the Gauss' trick and end up with three recursive calls instead of four. This yields a O(n*logn) complexity. | Apply the Gauss' trick and end up with three recursive calls instead of four. This yields a O(n*logn) complexity. <font color=darkkhaki>It if was four, the recursive complexity it would have been O(n<sup>2</sup>)</font>. | ||
Revision as of 23:06, 18 September 2021
Internal
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