a Las Vegas algorithm
Imagine a card trick that always ends with the right card on top, but takes a different number of shuffles each time you perform it — sometimes quick, sometimes you fiddle for a while. A Las Vegas algorithm is like that: it flips coins along the way, and the answer it gives is always correct, but how long it runs depends on luck. You can trust the output completely; you just cannot promise exactly when it will finish.
Precisely: a Las Vegas algorithm uses randomness and always returns a correct result (or honestly reports failure and retries), while its running time is a random variable. We usually summarize it by its expected running time — the average over the algorithm's own coin flips, for each fixed input. Randomized quicksort is the classic case: it picks a random pivot each time, always sorts correctly, and runs in O(n log n) expected time, though an unlucky run of pivot choices can still take O(n^2). A simple template is generate-and-test: keep making a random guess and checking it, returning the first guess that passes — for example, repeatedly drawing a random element until you draw one that is not a duplicate.
Las Vegas is the right model when a wrong answer is unacceptable but a variable wait is fine — sorting, searching, building a data structure. The cost you accept is uncertainty in time, not in correctness. The honest caveat: expected time is an average over the coins, not a worst-case guarantee, so a single run can be slow; and the analysis assumes a source of truly random bits, which real pseudo-random generators only approximate.
To pick a random element not equal to a forbidden value x in an array where x is rare: repeatedly draw a uniformly random index and return its element if it is not x. Each draw succeeds with probability close to 1, so the expected number of draws is just over 1 — and the returned element is guaranteed to differ from x.
Always-correct output, random running time: the hallmark of Las Vegas.
Las Vegas guarantees the answer, not the clock. Quoting an expected O(n log n) does not rule out a rare slow run; if you also need a hard time cap, you must cut the algorithm off and accept a possibility of failure, which turns it into Monte Carlo.