[ccleve]

Ok, 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.

[SkiFire13]

> 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.

[svat]

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.

[inkysigma]

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.

[pfdietz]

Adding up those n1 numbers, each at least n2 digits long, takes O(n1 * n2) time.

[GuB-42]

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

[mgaunard]

You're missing the fact that "multiplying a digit with a number" is not a single operation.

[ccleve]

No, that's taken into account.

[evandijk70]

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

[pdpi]

You’re missing the O(1) space complexity.

[floxy]

             1234567890 
           x     111111
           ------------
             1234567890
            12345678900
           123456789000
          1234567890000
         12345678900000
      + 123456789000000
      -----------------
    137,174,072,825,790 

...looks like O(n^2).

[ccleve]

Once the longer number starts repeating digits, then it's not n^2 anymore. Multiplies get replaced with lookups. And we're only counting the multiplies. That's all they counted in the article. Not the adds, not the shifts.

[CaptainNegative]

They don't count the additions or shifts because they're both linear time operations, and thus provably at least as fast as multiplication (both in an asymptotic and exact sense). In any case where multiplication is super-linear, this means that addition and shifting are are not the temporal bottleneck at any stage in the algorithm where you have a constant number of those operations surrounding at least one multiplicative recursive call (on numbers of similar magnitudes).

If additions were truly free, an even easier optimal algorithm would just be repeated addition involving zero multiplications.

[cvz]

The complexity of Karatsuba's algorithm, because it's a recursive one that gets "wider" at every level, is dominated by the width of that recursion. The top level always has a small number of operations, so we don't explicitly count them there, but the bottom has the truly huge number of operations that contribute to the algorithm's complexity, because each level of recursion dramatically increases the number of operations. Some number of those operations (most of them, in fact) will be single-digit additions.

Memoizing number-by-digit multiplication doesn't make multiplication O(1) because one must still do an N-digit addition (which is O(N)) for each digit.

[chowells]

The slowest multiplications are always when the two numbers are about the same size... That is to say, the case you're talking about doesn't happen.

[aaronbwebber]

your algorithm for multiplication involves doing multiplication?

[eru]

You might want to learn about recursion. It'll blow your mind.

[SideQuark]

… which needs a terminating case, which cannot be not defined as the same recursion.

[eru]

When talking informally, people often omit mentioning the base case when it's obvious or trivial.

Btw, your recursion doesn't necessarily need a terminating case.

See eg this definition of the list of Fibonacci numbers in Haskell:

    fibs :: [Integer]
    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

[SideQuark]

That's not recursion. And reversing arrows on this category turns base cases into co-base, or start cases, (and these are still often called base cases in the literature), so it is still required.

Reversing arrows again, back to recursion, you have exactly the standard labeled bases case (well, cases in your code), and reversing arrows doesn't magically change algorithms or invent new structure, so it completely equivalent in the category.

For that code, the 1:1:... is exactly the terminating/starting point, reversing arrows in the category does nothing to change the requirements.

[wizzwizz4]

Strictly-speaking, that's corecursion.

[eru]

Of course. But it's close enough as a reply to "your algorithm for multiplication involves doing multiplication?"