ABSTRACT
A randomized algorithm is one that makes random choices during its execution. The behavior of such an algorithm may thus, be random even on a fixed input. The design and analysis of a randomized algorithm focuses on establishing that it is likely to behave “well” on every input; the likelihood in sucha statementdependsonlyon theprobabilistic choicesmadeby thealgorithmduring execution and not on any assumptions about the input. It is especially important to distinguish a randomized algorithm from the average-case analysis of algorithms,where one analyzes an algorithm assuming that its input is drawn from a fixed probability distribution.With a randomized algorithm, in contrast, no assumption is made about the input. Two benefits of randomized algorithms have made them popular: simplicity and efficiency.
For many applications, a randomized algorithm is the simplest algorithm available, or the fastest, or both. In the following text, we make these notions concrete through a number of illustrative examples. We assume that the reader has had undergraduate courses in algorithms and complexity,
