edited by
13,564 views
43 votes
43 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?

  1. $O(n)$
  2. $O(n \log n)$
  3. $O(n^2)$
  4. $O(n!)$
edited by

4 Answers

Best answer
48 votes
48 votes

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.

edited by
49 votes
49 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
edited by
1 votes
1 votes
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).
–1 votes
–1 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)

Answer:

Related questions

25 votes
25 votes
2 answers
3
Kathleen asked Sep 14, 2014
10,417 views
Which of the following requires a device driver?RegisterCacheMain memoryDisk
37 votes
37 votes
3 answers
4
Kathleen asked Sep 14, 2014
12,501 views
Where does the swap space reside?RAMDiskROMOn-chip cache