What is the Space Complexity of Tail Recursive Quicksort?

Question

Looking at the following tail recursive quicksort pseudocode

QuickSort(A[1, ..., n], lo, hi)
Input: An array A of n distinct integers, the lower index and the higher index
         // For the first call lo = 1 and hi = n
Output: The array A in sorted order

If lo = hi return
         // The array A is already sorted in this case
If lo > hi or indices out of the range 1 to n then return

Else
      Pick an index k in [lo,hi] as the pivot
              // Assume that this can be done using O(1) cells on the stack
      i = Partition(A[lo, ..., hi], k)
              // Use in-place partitioning here so assume that this can be done
              // using O(1) space on the stack

If i - lo <= hi - i
      QuickSort(A, lo, i-1) // sort the smaller half first
      QuickSort(A, i+1, hi)
Else
      QuickSort(A, i+1, hi) // sort the smaller half first
      QuickSort(A, lo, i-1)

Assuming that the pivot is chosen adversarially each time I analyzed that it should have a space complexity of O(logn) [which I am not entirely sure is correct], but how would the space complexity be affected if the pivot is then chosen uniformly at random? I am fairly new to understanding space complexity over time complexity, so any feedback is appreciated!

Answer 1

In the worst case the space complexity will be $\Theta(n)$. The first recursive call to quicksort is not optimized hence the stack space of the current call is not reused. This can happen $\Theta(n)$ times if i is always hi.

If the pivot is selected uniformly at random then the space required will be $O(\log n)$ with high probability, since the recursion depth will be $O(\log n)$.

Answer 2

If you either use a compiler that supports tail recursion, or make the small change not to use recursion for the larger partition at all, the recursion depth depends on the sizes of the smaller intervals.

The worst case for recursion depth is the case that each partition divides your subarray exactly in half, making the depth $log_2 (n)$. The best case for recursion depth is the case that each partition divides your subarray into n-1 and 1 items, recursion depth = 1 (obviously the absolutely worst case for execution time).

So this is a bit paradoxical: Best case space complexity = worst case time complexity. But on the other hand, worst case space complexity = log n is so little that nobody cares about the space complexity. As long obviously as people don't make the mistake of sorting the larger partition first.

Without eliminating the recursion for the larger half, the worst case for recursion depth is n, and the order of the calls doesn’t matter.

Usually you can’t make an assumption that values would be different, so the quality of your partition function is important. Some will misbehave with many identical values.