Karatsuba Multiplication: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
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

Playground

https://github.com/ovidiuf/playground/tree/master/learning/stanford-algorithms-specialization/01-karatsuba
[Next]