0 votes 0 votes Algorithms algorithms sorting-algorithms-quicksort sorting asymptotic-notation + – iarnav asked May 27, 2019 iarnav 1.0k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply srestha commented May 27, 2019 reply Follow Share 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)$ 2 votes 2 votes iarnav commented May 30, 2019 reply Follow Share 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? 0 votes 0 votes srestha commented May 30, 2019 reply Follow Share @iarnav Randomized Algorithm chapter 0 votes 0 votes iarnav commented May 30, 2019 reply Follow Share Thanks, Q! 0 votes 0 votes Please log in or register to add a comment.