Oh, and if you want to be pedantic about the matter, there is no such thing as O(1) space, because you need log N bits to hold the pointer to the input in memory.