[kspiteri]

> Not if N=1 ;)

> (A constant amount is of course independent of N anyway!)

When using O notation, we're doing asymptotic analysis and n can be arbitrarily large. If you have an arbitrarily large pointer, you cannot store the pointer in a constant number of bits. If your pointer is 64-bits long, you're cannot handle n > 2^64. That is why I said you need O(log n) rather than O(1).

[Strilanc]

A common implicit assumption in complexity analysis is that machine words can hold O(lg n) bits, and that those words can be operated on in constant time.

Lots and lots of algorithms gain an extra lg(n) factor if you drop that assumption.

e.g. http://blog.computationalcomplexity.org/2009/05/shaving-logs...

[to3m]

Well, that's certainly an unusual way of looking at it! Pointers are usually assumed to be "large enough" when you do this sort of analysis, with the data being assumed to fit into the available address space (if you're even thinking about such issues). But I see your thinking now!