GATE CSE 2001 | Question: 1.14

Question

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using Randomized quicksort?

• A. $O(n)$
• B. $O(n \log n)$
• C. $O(n^2)$
• D. $O(n!)$

Comments

https://cs.stackexchange.com/questions/35994/why-does-randomized-quicksort-have-on-log-n-worst-case-runtime-cost

Answer 1

Correct Option: C
There are two cases, when Randomized Quick Sort will result into worst case time complexity of $O(n^{2})$

1. When all elements are same in the input array, Partition algorithm will divide input array in two sub-arrays, one with $n-1$ elements and second with $0$ element. There is an assumption here that, we are using the same partition algorithm without any modification.
    
2. If the randomised pivot selector happens to select the smallest or largest element N times in a row, we will get the worst possible  performance. Though the probability of this particular case is about $\frac{2^{n-1}}{n!}.$

PS: Option D is also correct here as $n^2 = O(n!)$ though $(C)$ is a better choice.

Comments

@Manu Thakur

I've only one doubt

How did u get the probability that every time the random number generator picks index of smallest/largest number as $\frac{2^{n-1}}{n!}$?

---

@aditi19

In every pass we have 2 choices for worst case, choosing either smallest element or greatest element as pivot... Likewise for n-1 passes..Remaining one element will be in correct position after n-1 passes.. so $2^{n-1}$..   And $n!$ corresponds all possible orders.

---

got it.... thanks

---

The probability is same as getting a skewed binary search tree. :)

The number of possible skewed binary search trees with 'n' nodes = 2$^{n-1}$

The probability is $\frac{2^{n-1}}{n!}$

Ex:

For 46,12,8,6 we have 8 skewed trees possible as mentioned below.

46,12,8,6 => l,l,l

46,12,6,8 => l,l,r

46,8,12,6 => l,r,l

46,6,8,12 => l,r,r

6,46,12,8 => r,l,l

6,8,46,12 => r,r,l

6,46,8,12 => r,l,r

6,8,12,46 => r,r,r 

---

n2=O(n!)n2=O(n!) though (C)(C) is a better choice.

More correct statement is 

n2=O(n!)n2=O(n!) though (C)(C) is a $\textbf{more tightest choice}$ choice here.

---

When all elements are same in the input array, Partition algorithm will divide input array in two sub-arrays, one with n−1n−1 elements and second with 00 element. 

Is this statement also means that worst case occurs only when the array is sorted in increasing or decreasing and choosing either small or large element as the pivot?

Can someone please verify this.

---

if the largest element is selected as pivot once will it not be excluded next time how can it repeat multiple times as we will apply quick sort on the remaining part right @Deepakk Poonia (Dee)

@Manu Thakur

---

can some one brief the second point more lucidly

---

@Deepak poonia  sir,how the probability has come

---

@samarpita Suppose we have $n$ elements.

First time: We have $n$ elements. We can either pick the smallest or the largest element (to get the worst case). Thus probability of picking the pivot = $2/n$

2^nd Time: We now have $n-1$ elements (b/c we already picked one element as the pivot). Again we can pick either the smallest or the largest element. Thus probability of picking the pivot = $2/(n-1)$

3^rd Time: Similarly $2/(n-2)$

…

(n-1)th Time: $2/(n-1)$ [Here probability will be $1$, because getting either largest or smallest out of two no. has prob of 1 for sure]

nth Time: Probability will be $1$ [obvious]

Thus total probability: $2*2*2$...[n-1 times] $/ (n*(n-1)*(n-2)* … *1)$ = $\frac{2^{n-1}}{n!}.$

---

@Abhrajyoti00

(n-1)th Time: 2/(n−1) [ Here probability will be 1, because getting either largest or smallest out of two no. has prob of 1 for sure]

nth Time: Probability will be 1 [obvious]

2 nd time pivot selection : 2/(n – 1)

3^rd time: 2/(n – 2)

(n- 1) ^th time: 2/ (n – (n – 2)) = 2/2 = 1

n ^th time pivot selection is not required.In this case, maximum only (n-1) time pivot selection is required to sort the array.

Thus total probability: 2∗2∗2...[n-1 times] /(n∗(n−1)∗(n−2)∗…∗1) = (2^(n-1))/ n!

---

Yes @Argharupa Adhikary. Although it’s not wrong to take n ^th time probability. But it’s not reqd. as it is always the smallest/largest.

Answer 2

In worst case, we may pick pivot elements in the increasing order (input also given in sorted order) which will result in running time of O($n^{2}$)

Both the deterministic and randomized quicksort algorithms have the same best-case running times of O($nlogn$) and the same worst-case running times of O(n$^{2}$).The difference is that with the deterministic algorithm, a particular input can elicit that worst-case behavior.  With the randomized algorithm, however, no input can always elicit the worst-case behavior.  The reason it matters is that, depending on how partitioning is implemented, an input that is already sorted--or almost sorted--can elicit the worst-case behavior in deterministic quicksort.

source: Thomas Coremen

Ans. C

Comments

Randomized quick sort picks the pivot randomly so in best case and avg case it gives O(nlogn) time complexity but stil in worst case there is a chance that it may select smallest element as pivot..so O(n^2) in worst case

---

@arjun sir i did not get the point...."expected num of comparision"

---

In Random Quick Sort

All these cases may come . ie '

In worst case, we may pick pivot elements in the increasing / decreasing order

Hence it is $O(n^{2})$ and $\Omega(n \log n)$

Answer 3

Randomized quicksort has expected time complexity as O(nLogn), but worst case time complexity remains same. In worst case the randomized function can pick the index of corner element every time.

Hence O(n^2).

Answer 4

The running time of Randomized QUICKSORT when all elements of array A have the same value will be equivalent to the worst case running of QUICKSORT since no matter what pivot is picked, QUICKSORT will have to go through all the values in A. And since all values are the same, each recursive call will lead to unbalanced partitioning.

Thus the recurrence will be:

T(n)=T(n−1)+Θ(n)

T(n)=Θ(n2)