Las Vegas algorithm

A Las Vegas algorithm is a randomized algorithm that always returns a correct result if it terminates. The term was introduced in 1979 by László Babai related to permutation of the vertices as a variant of Monte Carlo algorithms.

There are two definitions for Las Vegas algorithms and their time complexity:

• If the random bits only have an effect on the procedure of the algorithm, the Las Vegas algorithm always returns a correct result if it terminates. The time complexity is a function of a random variable, in this case. A well-known example is the Random Quicksort algorithm that chooses his pivot element at random, but its output is always sorted.
• If the result of the calculation of an algorithm with a probability is correct and the algorithm at the same time with a probability returns no result, then it is a Las Vegas algorithm.