GATE Overflow Test Series | Algorithms | Test 1 | Question: 17

Question

For quick sort pivot selection you are provided with an buggy implementation of Median select, which can return any element between $(n/3)^{rd}$ smallest and $(2n/3)^{rd}$ smallest in $O(n)$ time. With this function to choose the pivot, which of the following is/are TRUE for the QuickSort implementation? (Mark all CORRECT choices)

• A. In best case it can run in $O(n)$ time
• B. In worst case it will take $\Theta(n^2)$ time
• C. In worst case it will take $\Theta(n \log n)$ time
• D. In best case, it will run in $\Omega(n \log n)$ time

Comments

It means that “All the elements same” case also cannot be possible here ?

---

@Udhay_Brahmi why it will be B?

It will always be $\Theta(n lgn)$.

---

In the question, it is told that for selecting a pivot between (n/3)rd smallest and (2n/3)rd smallest we need O(n) time. Let's suppose after applying buggy implementation of Median select we get (n/3)rd + 1 smallest element. After that, we moved that (n/3)rd +1 element at the beginning in O(1) tym, just exchange the position. After that we will apply partition algo, which will take O(n) tym.

So the time complexity will be:

T(n) = T($\frac{n}{3}$) + T($\frac{2n}{3} – 1$) + n(for pivot selection) + n(for partition algo)

T(n) = T($\frac{n}{3}$) + T($\frac{2n}{3} $) + n

T(n) = O(n $lg_{\frac{3}{2}}$n) and T(n) = $\Omega (n lg_{3} n)$

So we can say T(n) = $\Theta (n lgn)$.

Answer 1

Worst case complexity of quick sort occurs in 2 cases, when smallest or largest element of array is chosen as pivot element. Now, both the smallest and largest elements of array cannot lie between (n/3)rd smallest element and (2n/3)rd smallest element of array. So both the case of worst cases are avoided and hence worst case can’t be O(n^2).

So answer is C, D

Comments

This is not the case here

The pivot what you are getting everytime you are getting it in linear that

that is why the recurrence relation always gives

T(n) = T(n/k) + T(n-(n/k)) + cn which gives $\Omega({nlogn})$ , $\Theta({nlogn})$