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.
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.
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
The lookup table would not work for that case
1234567890
x 111111
------------
1234567890
12345678900
123456789000
1234567890000
12345678900000
+ 123456789000000
-----------------
137,174,072,825,790
...looks like O(n^2).If additions were truly free, an even easier optimal algorithm would just be repeated addition involving zero multiplications.
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.
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)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.