- This is the idea behind opinion polling, where we sample a small number of people as a proxy for the full population. The result should be representative for the full set.
- The worst-case set of keys that all get hashed to the same bucket.
- Suppose we randomly select our hash function from a large family of good ones as the first step of our algorithm.
- Randomization can also be used to drive search tech- niques such as simulated annealing.
Classification of randomized algorithms
1. Las Vegas algorithms
- Guarantee correctness
- Usually (but not always) efficient
- i.e. Quicksort
2. Monte Carlo algorithms
- Provably efficient
- Usually (but not always correct)