4 ms·

This takes (worse than) quadratic time.

• thehappypm 4y ago
  I’m not sure it does, in the best case. There are d additions, so the addition is linear time. Each multiplication is potentially quadratic, but it seems optimizable since it’s never multiplication of two large numbers—always one large and one small number.
  • singron 4y ago
    Each addition is linear in d, but there are d additions, so it's already quadratic before you even consider the multiplications. In a power-of-2 base, the result of the multiplication is a constant number of digits (because the multiplication is just a shift of a single digit), so the additions could each be constant time in that case.
  • tylerhou 4y ago
    One mistake is assuming that the additions take constant time, but really they take ~n time each because you're adding up n-bit integers. If you accumulate your results from left to right you're adding an n-bit integer with a (~n-3)-bit integer, which results in an n-bit integer, which you add with an (~n-6)-bit integer, and so on. This sums up to \Theta(n^2). Another issue you have not accounted for is how you convert to base two. If you want the final product to be in base two, your additions have to be in base two, so the result of your multiplications have to be in base two, which means you will have to convert 1000, 100, 10, 1 into base two as well. Again this takes \Theta(n^2) time if you cache results (1000_2 = 100_2 *_2 10_2): you're doing n operations, and the cost of each operation is 1, 2, 3, 4, ..., n (times some constant. 10^(n-1) * 10 all in base two takes \Theta(n) time). But it's not actually worse than O(n^2), my mistake.
    • thehappypm 4y ago
      They’re probably seeing real-world performance being pretty good with this approach for some other reason then, perhaps it’s quadratic but those additions and multiplications are fast in practice so the O(n^2) badness doesn’t come up for a while