in place quick sort has O(n) or O(logn) space complexity

Question

This Wikipidea article http://en.wikipedia.org/wiki/Quicksort#In-place_version suggests that O(logn) is the space time complexity for in place sort and http://futur3googl3r.blogspot.com/2008/08/google-interview-questions.html this interview site suggests it is O(n). I think the answer is O(n) but wanted to know if I am right.

Answer 1

In both articles, the space complexity that they are referring to is of the extra space (not counting the space needed to store the original array). This extra space may come from the call stack, in addition to the common case where an extra array is declared. Each recursive call will create a stack frame on the call stack, which takes up space, and the number of stack frame is dependent on input size n, so it needs to be counted.

Let us use the Wikipedia article for reference, since the blog is quite inconsistent as pointed out by @Jim Mischel.

For in-place quick sort, modifying from the naive implementation will give O(log n) extra space on average, instead of the O(n) extra space (in all cases) in the naive implementation. The worst case complexity of extra space, as pointed out correctly by the blog¹, is O(n), when the algorithm encounters its worst case (a sorted list; there will be n recursive calls so the call stack will take up O(n) extra space).

¹: (Thanks to @rici for pointing out) However, the blogger is only correct if we assume an implementation without the optimization as mentioned in the Wikipedia article. It is possible to improve the algorithm to use O(log n) extra space in worst case, by recursing on the smaller portion first and implementing a tail call for the longer portion. Since the smaller portion is always less than half of the input size, there will be at most O(log n) recursive calls. Assuming tail-call optimization is done, the longer portion will reuse the current stack frame without incurring extra spaces. If tail-call optimization is not done, we can always write an iterative implementation with explicit stack.