[blackhole]

This is completely missing the point of Big-Oh notation. If you start trying to analyze how long integer operations take, ALL your computational complexity analysis falls apart for any sufficiently large integer arithmetic for any algorithm. This is precisely why such operations are ignored, because it becomes completely impossible to do any meaningful platform-independent analysis if you try to take that into account.

That's not to say you shouldn't take it into account, but the algorithm he described is, in fact, O(log(n)) time. It just is. That's how the math works. Now, you should note that the O(log(n)) time constraint does not take into account arbitrary integer size which will cause progressively larger constant factors to influence the efficiency of the algorithm... but it is still a O(log(n)) algorithm.

[stephencanon]

My analysis holds for any implementation for which you can perform O(1) addition and multiplication of integers of some fixed-size. That's just about as platform-independent as you can get, but it still captures the real complexity of the operation in a way that handwavy "pretend you can do arbitrary arithmetic in O(1)" analyses do not.

This isn't simply my viewpoint on the subject; even the very theoretical textbook by Papadimitriou and Vazirani takes this approach to the question (see exercise 0.4 and note that everything is carried out in terms of the complexity of arbitrary-size integer multiplication M(n)).

[wging]

>progressively larger constant factors

If they are getting progressively larger with larger inputs, then they are not in fact constant factors.