A Las Vegas algorithm is an algorithm that guarantees the correctness of a solution, but does not guarantee the running time.

Contrast this with a Monte Carlo algorithm, which guarantees a solution within a certain running time, but does not guarantee a correct solution, only the probability that a solution is correct.