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

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.