in DS edited by
1,934 views
1 vote
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?
in DS edited by
1.9k views

4 Comments

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
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
I think you are right if the partition is always done in the ratio of 1:n-1 then the sorting algorithm would take O(n) stack records.
0
0
@surajumang08 This is the answer I was expecting.

"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"

This was introduced in 1978 by Sedgewick, Right?

Can you please elaborate the statement?
0
0

3 Answers

0 votes
0 votes

O(n2) worst case tym complexity of quick sort when input is sorted

1 comment

@ eyeamgj I am not asking for time complexity but space complexity of quick sort in worst case
0
0
0 votes
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
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).

Related questions