# What is the Space Complexity of Tail Recursive Quicksort?

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!