Randomized Algorihm

we call an algorithm randomized if its behavior is determined not only by its input but also by values produced by a random-number generator.

We distinguish these algorithms from those in which the input is random by referring to the running time of a randomized algorithm as an expected running time.

In general, we discuss the average-case running time when the probability distribution is over the inputs to the algorithm, and we discuss the expected running time when the algorithm itself makes random choices.