1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

Since worst case space complexity of $\Theta(n)$ could be a problem, you can make a slight modification to the Qicksort algorithm: Partition the array, then sort the smaller half recursively, and sort the larger half iteratively. Roughly:

Sort (range r)
    While r contains two or more elements
        Partition range r
        Sort (smaller sub partition)
        r = larger sub partition 

This reduces the worst case space required to $\Theta(\log n))$. It does not help with the worst case execution time.

$\endgroup$
1
  • $\begingroup$ (Brilliantly presented but for calling smaller and larger partitions halves.) $\endgroup$ – greybeard Apr 1 at 5:14
1
$\begingroup$

Here is quicksort in a nutshell:

  • 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)$.

$\endgroup$
3
  • $\begingroup$ Thank you for this explanation $\endgroup$ – Mj _ Mar 31 at 10:14
  • $\begingroup$ What do you mean by 'adversarially'? $\endgroup$ – Mj _ Mar 31 at 10:18
  • $\begingroup$ If an adversary whose goal is to foil the algorithm chooses the pivots, then it can force the recursion tree to have depth $\Omega(n)$. $\endgroup$ – Yuval Filmus Mar 31 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.