the worst-case running time of randomized algorithm is often the same as the worstcase running time of the nonrandomized algorithm the important difference is that good randomized algorithm has no bad inputs but only bad random numbers (relative to the particular inputthis may seem like only philosophical differencebut actually it is quite importantas the following example shows consider two variants of quicksort variant uses the first element as pivotwhile variant uses randomly chosen element as pivot in both casesthe worst-case running time is ( )because it is possible at each step that the largest element is chosen as pivot the difference between these worst cases is that there is particular input that can always be presented to variant to cause the bad running time variant will run in ( time every single time it is given an already-sorted list if variant is presented with the same input twiceit will have two different running timesdepending on what random numbers occur throughout the textin our calculations of running timeswe have assumed that all inputs are equally likely this is not truebecause nearly sorted inputfor instanceoccurs much more often than is statistically expectedand this causes problemsparticularly for quicksort and binary search trees by using randomized algorithmthe particular input is no longer important the random numbers are importantand we can get an expected running timewhere we now average over all possible random numbers instead of over all possible inputs using quicksort with random pivot gives an ( log )-expectedtime algorithm this means that for any inputincluding already-sorted inputthe running time is expected to be ( log )based on the statistics of random numbers an expected running-time bound is somewhat stronger than an average-case bound butof courseis weaker than the corresponding worst-case bound on the other handas we saw in the selection problemsolutions that obtain the worst-case bound are frequently not as practical as their average-case counterparts randomized algorithms usually are randomized alogrithms were used implicitly in perfect and universal hashing (sections and in this sectionwe will examine two uses of randomization firstwe will see novel scheme for supporting the binary search tree operations in (log nexpected time once againthis means that there are no bad inputsjust bad random numbers from theoretical point of viewthis is not terribly excitingsince balanced search trees achieve this bound in the worst case neverthelessthe use of randomization leads to relatively simple algorithms for searchinginsertingand especially deleting our second application is randomized algorithm to test the primality of large numbers the algorithm we present runs quickly but occasionally makes an error the probability of error canhoweverbe made negligibly small random-number generators since our algorithms require random numberswe must have method to generate them actuallytrue randomness is virtually impossible to do on computersince these numbers will depend on the algorithmand thus cannot possibly be random generallyit suffices to produce pseudorandom numberswhich are numbers that appear to be random random numbers have many known statistical propertiespseudorandom numbers satisfy most of these properties surprisinglythis too is much easier said than done