Randomized Algorithms

Randomized algorithms are algorithms that make random choices during execution to achieve correct or approximately correct results — typically with lower worst-case complexity, simpler implementation, or both, compared to deterministic alternatives.

The key insight: introducing controlled randomness often breaks the adversarial structure of worst cases. A deterministic sorting algorithm can be analyzed by an adversary who constructs the worst-case input. A randomized algorithm's behavior on any fixed input is a distribution — the adversary cannot guarantee a bad outcome without also controlling the random bits.

Randomized algorithms split into two classes. Las Vegas algorithms (like randomized quicksort) always produce correct output; randomness affects only runtime. Monte Carlo algorithms trade correctness probability for speed — the answer may be wrong, but the error probability is controllable. Most approximation algorithms are Monte Carlo in character.

The practical result: randomized algorithms routinely outperform the best known deterministic algorithms for graph problems, cryptography, primality testing, and data stream processing. The deeper result: the complexity class BPP (bounded-error probabilistic polynomial time) may or may not equal P — this is an open problem whose resolution would say something fundamental about whether randomness adds genuine computational power or merely convenience.