randomized quick-sort one common method for analyzing quick-sort is to assume that the pivot will always divide the sequence in reasonably balanced manner we feel such an assumption would presuppose knowledge about the input distribution that is typically not availablehowever for examplewe would have to assume that we will rarely be given "almostsorted sequences to sortwhich are actually common in many applications fortunatelythis assumption is not needed in order for us to match our intuition to quick-sort' behavior in generalwe desire some way of getting close to the best-case running time for quick-sort the way to get close to the best-case running timeof courseis for the pivot to divide the input sequence almost equally if this outcome were to occurthen it would result in running time that is asymptotically the same as the best-case running time that ishaving pivots close to the "middleof the set of elements leads to an ( log nrunning time for quick-sort picking pivots at random since the goal of the partition step of the quick-sort method is to divide the sequence with sufficient balancelet us introduce randomization into the algorithm and pick as the pivot random element of the input sequence that isinstead of picking the pivot as the first or last element of swe pick an element of at random as the pivotkeeping the rest of the algorithm unchanged this variation of quick-sort is called randomized quick-sort the following proposition shows that the expected running time of randomized quick-sort on sequence with elements is ( log nthis expectation is taken over all the possible random choices the algorithm makesand is independent of any assumptions about the distribution of the possible input sequences the algorithm is likely to be given proposition the expected running time of randomized quick-sort on sequence of size is ( log njustificationwe assume two elements of can be compared in ( time consider single recursive call of randomized quick-sortand let denote the size of the input for this call say that this call is "goodif the pivot chosen is such that subsequences and have size at least / and at most / eachotherwisea call is "bad nowconsider the implications of our choosing pivot uniformly at random note that there are / possible good choices for the pivot for any given call of size of the randomized quick-sort algorithm thusthe probability that any call is good is / note further that good call will at least partition list of size into two lists of size / and / and bad call could be as bad as producing single call of size