4.2k views

In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time complexity of the quick sort?

1. $\Theta(n)$

2. $\Theta(n \log n)$

3. $\Theta(n^2)$

4. $\Theta(n^2 \log n)$

edited | 4.2k views
+1
What if I take an array of size n with all elements equal??

That would lead to worst case irrespective of pivot selection.

So , will Time complexity be $\Theta (n^2)?$

$T(n)= O(n)$ pivot selection time $+ T(n/4 - 1) + T(3n/4)$

which'll give $\Theta\left(n \log n\right)$.

Pivot selection complexity is given in questions. Pivot being the $(n/4)$th smallest element, once it is found, we have two sub arrays- one of size $(n/4 - 1)$ and other of size $(3n/4)$ and for both of these we solve recursively.

answered by Boss (19.9k points)
edited
0
But the question doesnot mention the list in sorted order how can we say that the pivot divides the list like n/4 and 3n/4.
0
Plzzz Any one clarify my doubt
0

Read the question.. it is mentioned that

the (n/4)th smallest element is selected as pivot

So if it resides at its correct position then the list is divided like n/4 and 3n/4.

0
I got it thank you
0
@ Arjun sir can you explain how to interperet recurrence relation using statement and then how to solve it.if it is simple then am able to solve it using master theoram but if it is complicated then am fail plz help.
0
but it is not mentioned to take elements in sorted order
+1

"I tried the same ,  why masters method" failed here ?

0

Why master's theorem is not working here??

0

why here we assumed that it always be divided in t/4 and 3t/4 as pivot can be anywhwere not neccesaary to be at t/4 th position. @Gate Keeda @Debashish Deka    pls explain ?

as n/4th element smallest element can be at leftmost or rightmost position also. they asked for n/4th smallest element not n/4th position.

0
What if I say that at each level use O(n) time algo to find n/4 smallest element as pivot in this case complexity will be O(n^2logn).

Here, The correct ans is     O ( n log4/3(n))

answered by Loyal (6.7k points)
0
Explain .....
+1 vote

option b

answered by Boss (34.2k points)
Basically we have worst case in quick sort when all elements are same or sorted. If they are all same then we can't find the (n/4)th smallest element in it.

But if the value are 1 2 3 4 5.

We take pivot 1 here.  Then 2, 3, 4, and 5.

So, no of comparison is n-1 + n-2 + ... + 1.

So n^2 is complexity for worst case which is sorted
answered by (175 points)

1
2