Randomized Algorithm
Domain: Algorithms
🎯 Motivation
An algorithm that uses random numbers to make decisions. Often simpler and faster than deterministic alternatives, with high probability of correctness.
📋 Concrete Example
Randomised quick sort picks a random pivot. The worst case (O(n^2)) is possible but extremely unlikely. Average case is O(n log n) with high probability.
🔗 Analogy
Flipping a coin to choose which queue at the supermarket. You might not pick the fastest queue, but over many trips, your average wait time is good. Randomness avoids consistently bad choices.