edited by
2,410 views
1 votes
1 votes

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?
edited by

3 Answers

0 votes
0 votes

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

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

0 votes
0 votes
1 answer
1
LavTheRawkstar asked Jan 12, 2017
807 views
INSERTION-SORT (A, n) ⊳ A[1 . . n]for (j ← 2 to len(A) ){key ← A[ j];i ← j – 1 ; while (i 0 and A[i] key) { A[...
9 votes
9 votes
2 answers
3
vineet.ildm asked Nov 7, 2016
5,810 views
Why space complexity of heapsort is O(1)....and why not O(logn)..because of space required by recursion calls which is equivalent to height of the tree...where am i getti...
1 votes
1 votes
2 answers
4
vishal chugh asked Jan 24, 2018
1,734 views
What is the worst case time complexity to find kth smallest element into an array of ‘n’ element?