patternMinor
What is the space complexity of quicksort?
Viewed 0 times
thespacewhatquicksortcomplexity
Problem
What is the space complexity of quicksort?
I was doing some research and found some saying it is $O(1)$, some saying it's $O(\log n)$, and some saying $O(n)$. Not sure what to believe, even though $O(\log n)$ seems to make the most sense for me. Does it all depend on the pivot point that is chosen?
I was doing some research and found some saying it is $O(1)$, some saying it's $O(\log n)$, and some saying $O(n)$. Not sure what to believe, even though $O(\log n)$ seems to make the most sense for me. Does it all depend on the pivot point that is chosen?
Solution
Here is quicksort in a nutshell:
Each recursive call uses $O(1)$ words in local variables, hence the total space complexity is proportional to the height of the recursion tree.
The height of the recursion tree is always at least $\Omega(\log n)$, hence this is a lower bound on the space complexity. If you choose the pivot at random or using a good heuristic, then the recursion tree will have height $O(\log n)$, and so the space complexity is $\Theta(\log n)$. If the pivot can be chosen adversarially, you can cause the recursion tree to have height $\Theta(n)$, causing the worst-case space complexity to be $\Theta(n)$.
- Choose a pivot somehow.
- Partition the array into two parts (smaller than the pivot, larger than the pivot).
- Recursively sort the first part, then recursively sort the second part.
Each recursive call uses $O(1)$ words in local variables, hence the total space complexity is proportional to the height of the recursion tree.
The height of the recursion tree is always at least $\Omega(\log n)$, hence this is a lower bound on the space complexity. If you choose the pivot at random or using a good heuristic, then the recursion tree will have height $O(\log n)$, and so the space complexity is $\Theta(\log n)$. If the pivot can be chosen adversarially, you can cause the recursion tree to have height $\Theta(n)$, causing the worst-case space complexity to be $\Theta(n)$.
Context
StackExchange Computer Science Q#138335, answer score: 7
Revisions (0)
No revisions yet.