alt Hacker NewsOk, maybe I don't understand the problem, but it seems obvious that it should never be greater than O(min(n1, n2) * 10), where n1 and n2 are the lengths in digits of each argument, and assuming we are multiplying decimal numbers.
Take the first digit of the longer number. Multiply it by the shorter number and store the result. Take the second digit of the longer number. If it matches the first digit, do a lookup of the last result and use that, else multiply and store. Repeat.
There will be a maximum of 10 * (length of the shorter number) multiplies, because there are only 10 unique digits. After that every operation is a lookup.
You could even do a tiny optimization by skipping the multiplication for the zero digit.
Worst case, the two numbers are the same length, in which case it's O(n/2 * 10), which is a heck of a lot better than O(n log n).
What am I missing here?
EDIT to respond to the comments: in the article, they are only counting the number of multiplies in the O() value. They are not including the adds.
Replies
By your reasoning, multiplying two numbers in binary involves no multiplication at all, because multiplying by 1 and multiplying by 0 are both trivial operations.
But obviously multiplying two n-bit binary numbers is not done in O(1) time, so "only counting the number of multiplies" is not a meaningful model, and not the model adopted by the researchers quoted in the article.
The final time complexity for Karatsubas does account for the addition via the master theorem and gives you something less than n^2. It’s just in some sense the recursion is dominant so we add to the exponent. As a result, I think the article is just talking about counting multiplications since it’s in some sense the “expensive” operation in the both the recursive karatsuba and the regular grade school method.
The reason the adds don't count is not because they arbitrarily decided to ignore them.
Addition is O(n), multiplication is more than O(n), by the nature of the big-O notation, when you have to do a series of operation, you only have to count the ones with the highest complexity. So in the Karatsuba example where the formula involves both additions and (recursive) multiplications, the additions don't count only because the multiplications dominate.
Or, as a formula, O(n log n) + O(n) = O(n log n), and btw O(n/2*10) = O(n), in big-O, constant factors don't count
Adding up those n1 numbers, each at least n2 digits long, takes O(n1 * n2) time.
You're missing the fact that "multiplying a digit with a number" is not a single operation.
Not an expert, but I think the algorithm works for any base, not just 10. The python implementation uses base 2^30 for their multiplication. Base 10 is just a convenient illustration
The lookup table would not work for that case
You’re missing the O(1) space complexity.
1234567890
x 111111
------------
1234567890
12345678900
123456789000
1234567890000
12345678900000
+ 123456789000000
-----------------
137,174,072,825,790
your algorithm for multiplication involves doing multiplication?
> EDIT to respond to the comments: in the article, they are only counting the number of multiplies in the O() value. They are not including the adds.
This simplification relies on the fact that after making a multiplication the cost of merging it with the result of another is always less than the cost of performing the multiplication, so it doesn't change the overall complexity.
This is not true in your proposed algorithm: a lookup is O(1), but merging is O(N), so you cannot do the same simplification and have to count the complexity of performing adds as well.