To guess if a huge crowd is mostly adults, you don't count everyone — you sample a few at random. Randomized algorithms flip coins to compute answers fast, usually right, and with tiny odds of being wrong that you can shrink as small as you like.
Randomness as a tool
A randomized algorithm makes random choices during execution. Surprisingly, randomness can yield simpler and faster algorithms than any known deterministic one. Two families: Las Vegas algorithms always return a correct answer but have random running time (e.g. randomized quicksort); Monte Carlo algorithms run in bounded time but may err with small probability.
Las Vegas: always correct, expected-time bound. Monte Carlo: always fast, small chance of a wrong answer — often driven arbitrarily low by repeating the algorithm.
Randomized quicksort picks a random pivot, giving expected O(n log n) regardless of input order — dodging the worst case that fixed-pivot quicksort hits on sorted data.
- An algorithm always returns the right answer, but its running time varies with the coin flips.
- Recall the two categories of randomized algorithm.
- Name which one this is.
What you should see: Always correct with random running time makes it a Las Vegas algorithm (as opposed to Monte Carlo, which is always fast but may err).