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.
(A constant amount is of course independent of N anyway!)
> (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).
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...