The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+20 votes

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?

- $O(n)$
- $O(n \log n)$
- $O(n^2)$
- $O(n!)$

+15 votes

Best answer

**Answer will be (C).**

There are following two cases, when Randomized Quick Sort will result into worstcase of time complexity $O(n^{2})$

- When all elements are same in the input array, Partition algo will divide input array in two sub-array, 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.

- If the randomised pivot selector happens to select e.g. the smallest element N times in a row, we will get the worst possible performance. Though the probability of this particular case is about $\frac{1}{n!}$ "

PS:- If the partitioning is **unbalanced**, Quick Sort algorithm runs asymptotically as slow as **Insertion Sort **i.e $O(n^{2})$

+32 votes

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

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

+6

Yes. That is correct. O(n log n) is the **EXPECTED** number of comparisons when pivot is chosen randomly.

0

**But I have read that it gives O(n^2) only when pivot is selected as first or last element in an already sorted list, so i think here ans should be O(n logn) as they are talking about randomized quick sort here... pls tell me if i am correct or not?**

–2 votes

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)

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 584
- Exam Queries 571
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,115 questions

53,224 answers

184,678 comments

70,474 users