Content deleted Content added
No edit summary |
note that \log23 \approx 1.585 |
||
Line 1:
The '''Karatsuba''' [[multiplication algorithm]], a technique for quickly multiplying large numbers, was discovered by A. Karatsuba and published together with Yu. Ofman in 1962. Its [[time complexity]] is [[Big O notation|Θ]]<math>(n^{\log_23})</math>. This makes it faster than the classical [[Big O notation|Θ]](''n''<sup>2</sup>) algorithm (<math>\log23 \approx 1.585</math>), although for small numbers it is not as fast.
| |||