Randomized algorithm

Summary

A randomized algorithm is an algorithm that may make random choices, such as coin flips, while it runs. Its running time or its output is then a random variable, and one studies its expected running time or its probability of error. A Las Vegas algorithm always answers correctly but has a random running time. A Monte Carlo algorithm has a bounded running time but may err with small probability. Randomness often gives simpler or faster algorithms than the best known deterministic ones. It leads to complexity classes such as BPP, RP and ZPP.