[kspiteri]

You just need a constant number of pointers. This requires O(log n) scratch space because a pointer can be stored in O(log n) space.

[to3m]

Not if N=1 ;)

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

[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).