Content deleted Content added
Line 332:
Bigger numbers ''x''<sub>1</sub>''x''<sub>2</sub> can be split into two parts ''x''<sub>1</sub> and ''x''<sub>2</sub>. Then the method works analogously. To compute these three products of ''m''-digit numbers, we can employ the same trick again, effectively using [[recursion]]. Once the numbers are computed, we need to add them together (step 5.), which takes about ''n'' operations.
Karatsuba multiplication has a time complexity of [[Big O notation|O]](''n''<sup>log<sub>2</sub>3</sup>)
Later the Karatsuba method was called ‘[[divide and conquer algorithm|divide and conquer]]’, the other names of this method, used at the present, are ‘[[binary splitting]]’ and ‘[[dichotomy principle]]’.
| |||