Flipping coins on purpose
A randomized algorithm makes random choices during execution. Randomness is used not for variety but to gain a guarantee that does not depend on the input being friendly: an adversary who picks the worst input cannot also pick the algorithm's coin flips.
Two families
- Las Vegas algorithms always return a correct answer; only their running time varies with the random choices. Randomized quicksort is the classic case: picking a random pivot makes the expected running time good regardless of input order.
- Monte Carlo algorithms have a bounded running time but may return a wrong answer with small probability. Running them several times with independent randomness drives the error probability down as low as desired.
Why it helps
A deterministic algorithm has a fixed worst case input that an adversary can supply on purpose. A randomized algorithm spreads its behavior over many possible coin flips, so no single input is reliably bad; the bad cases exist but are rare and unpredictable. This often yields simpler code than the deterministic algorithm that achieves the same guarantee, such as randomized pivoting versus median of medians.
Key idea
Randomized algorithms use random choices so no input is reliably the worst case; Las Vegas variants are always correct with variable time, while Monte Carlo variants are fast with a tunable error probability.