Q67: Case in Quicksort

You can go through Q50 & Q51 before this one.

Question #67: Assume that after every step of Quick Sort, the split happens in such a way that one side contains 90% of the elements and the other side contains 10%. What will be the complexity of the quick sort algorithm in such a scenario?

Options:

1. O(n)
2. O(n³)
3. O(n²)
4. O(n log(n))

Solution: Although this looks like a bad split, but still, quick sort would run in O(n log(n)) time. Following will be the recursive tree that will be formed.

In fact, any constant split (e.g. 99:1) would yield the same time complexity as the normal case, making option 4th the correct answer.

Q51: Best case of Quick Sort

This is in continuation of Question #50

Question #51: What is the best case complexity of the quick sort?

1. O(n)
2. O(n³)
3. O(n²)
4. O(n log(n))

Solution: In the best case, we will always have the pivot element as the median, and it will divide the two sub-arrays into two equal parts. Hence, the recursive equation will be:

• T(n) = T(n/2) + T(n/2) + n
• T(n) = 2T(n/2) + n
• T(n) = 2( 2*T(n/4) + n/2) + n
• T(n) = 4T(n/4) + 2n
• T(n) = 8T(n/8) + 3n
• …
• T(n) = n*T(n/n) + log(n) * n
• T(n) = O(nlog(n))

Hence, the correct answer is D

Q50: Worst case of Quick sort

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(n³)
3. O(n²)
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) = cn² + k
• T(n) = O(n²)

Hence, the correct answer is option 3.