thusin the best caset has height (lognand quick-sort runs in (nlogntimewe leave the justification of this fact as an exercise ( - the informal intuition behind the expected behavior of quick-sort is that at each invocation the pivot will probably divide the input sequence about equally thuswe expect the average running time quick-sort to be similar to the best-case running timethat iso(nlognwe will see in the next section that introducing randomization makes quick-sort behave exactly in this way randomized quick-sort one common method for analyzing quick-sort is to assume that the pivot will always divide the sequence almost equally 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 bestcase running time that ishaving pivots close to the "middleof the set of elements leads to an (nlognrunning 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 almost equallylet 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 last element of swe pick an element of at random as the pivotkeeping the rest of the algorithm unchanged this variation of quicksort is called randomized quick-sort the following proposition shows that the expected running time of randomized quick-sort on sequence with elements is (nlognthis 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 (nlognjustificationwe assume two elements of can be compared in ( time consider single recursive call of randomized quick-sortand let denote