#CLRS #Algorithm Doubt about randomized QuickSort.

Question

Comments

from clrs

Consider, on the other hand, the randomized algorithm that first permutes the candidates and then determines the best candidate. In this case, we randomize in the algorithm, not in the input distribution. Given a particular input, say A3 above, we cannot say how many times the maximum is updated, because this quantity differs with each run of the algorithm. The first time we run the algorithm on A3, it may produce the permutation A1 and perform 10 updates; but the second time we run the algorithm, we may produce the permutation A2 and perform only one update. The third time we run it, we may perform some other number of updates. Each time we run the algorithm, the execution depends on the random choices made and is likely to differ from the previous execution of the algorithm. For this algorithm and many other randomized algorithms, no particular input elicits its worst-case behavior. Even your worst enemy cannot produce a bad input array, since the random permutation makes the input order irrelevant. The randomized algorithm performs badly only if the random-number generator produces an “un- lucky” permutation.

So worst would be $O(n^{2})$ and best $O(nlogn)$ 

---

thanks srestha, do you recommend me the source from where you get this?

 

I mean, which page of CLRS and where is the A3 array which is mentioned?

---

@iarnav

Randomized Algorithm chapter

---

Thanks, Q!