yes in worst case, when tree is divided in n,n-1,n-2......1 then stack size will be maximum as O(n).

Reference-https://stackoverflow.com/questions/38487269/space-complexity-of-quick-sort

Dark Mode

2,021 views

1 vote

First read it properly. I am not asking a specific question about space complexity.

Question: What is worst case space complexity of quick sort?

Everywhere it is showing O(logn).

My understanding about it:

I know that Quick sort algorithm doesn't request extra space except for stack records.

so, Space complexity will be O(logn) if partition is being done by half or n/2:n/2. So logn stack records.

But if partition is being done by ratio 1:n-1 which is worst case, wouldn't it be requesting for O(n) stack records?

yes in worst case, when tree is divided in n,n-1,n-2......1 then stack size will be maximum as O(n).

Reference-https://stackoverflow.com/questions/38487269/space-complexity-of-quick-sort

0

worst case space complexity of any general (naive) implementation of Quicksort is O(N) which occurs if the division is in the ratio you mentioned i.e 1:N-1 . you can refer this https://stackoverflow.com/questions/15034897/in-place-quick-sort-has-on-or-ologn-space-complexity

It also says that the worst case space complexity can be restricted to O(logN) by implementing a Tail call on the longer portion of the array

0

0

0 votes

With a little effort, we can limit the maximum depth of recursion to approximately Olg(n), even in the worst case.

- Then the extra space required will be O(lg(n)) — insignificant compared to the O(n) space for the array being sorted.
- Note, however, the worst case running time remains O($n^{2}$)

voidquicksort2( T[] A, Integer left, Integer right) { while ( left < right ) { q = partition(A,left,right); if ( q-left < right-q ) { quicksort2(A,left,q–1); // Recursive call sorts smaller sublist left = q + 1; // Loop back to sort larger sublist } else { quicksort2(A,q+1,right); // Recursive call sorts smaller sublist right =q-1; // Loop back to sort larger sublist } }

Here with better programming using Tail call, we can limit the O(n) stack frame in worst case. Each time quicksort2() calls itself recursively, it does so only for the smaller of the two sublists. This means that each time the depth of recursion rises by one, the size of the input to quicksort2() is cut at least in half. Thus the depth of recursion cannot exceed lg(n).

That is the reason behind everywhere quicksort space complexity is written as O(log n). Because we can optimize the standard quicksort using tail recursion to limit the stack frame as maximum log n, still the time complexity in worst case remains same.

0 votes

You are correct.

A simple implementation of QuickSort makes two calls to itself and in worst case requires O(n) space on function call stack. The worst case happens when the selected pivot always divides the array such that one part has 0 elements and other part has n-1 elements.

Ref: https://www.geeksforgeeks.org/quicksort-tail-call-optimization-reducing-worst-case-space-log-n/

With tail call optimization and other things we can reduce stack space to O(log n).