Q50: Worst case of Quick sort

Posted on by bytesoftheday

Quick sort: In every step of Quick sort algorithm, we select a pivot and move all elements in such a way that pivot element reaches to the correct position. Assuming we are sorting in ascending order, then at the end of any step, all elements smaller than pivot elements are in the left side of the pivot and all elements greater than pivot are on the right side. This step takes O(n) time. Then we apply the same algorithm to the left sub-array and right sub-array.

 

Question #50: What is the worst case complexity of the quick sort?

  1. O(n)
  2. O(n3)
  3. O(n2)
  4. O(n log(n))

 

Solution:  The worst case is when the one of the sub-array is empty and the other sub-array contains n-1 elements. Hence, the recursive equation will be:

  • T(n) = T(n-1) + n
  • T(n) = T(n-2) + 2n
  • T(n) = T(n-3) + 3n
  • …
  • T(n) = cn2 + k
  • T(n) = O(n2)

Hence, the correct answer is option 3.