Worst-case space complexity of Quicksort should be set to O(n)
Closed this issue · 1 comments
luludak commented
Right now, the worst-case space complexity for Quicksort
, is set to O(log(n))
. This is not right - the average-case space complexity is Θ(log(n))
, but when you attempt to sort an already sorted list, this will lead into n recursive calls on the stack, thus the O(n)
worst-case space complexity.
luludak commented
Update: I searched more in detail on this, and I actually got that having an implementation with O(log(n))
auxiliary space is possible, with in-place partitioning and by sorting first the partition with the fewest elements.