Hacker News Reader

The second problem would be clearer if we knew how much scratch space we had. Is it zero? Is it O(1)? Is it O(n)?

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.

Not if N=1 ;)

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

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

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!

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

Can be solved with no extra storage just three ints or pointers.

Reply on news.ycombinator.com