[3] Babai[4] introduced the term "Las Vegas algorithm" alongside an example involving coin flips: the algorithm depends on a series of independent coin flips, and there is a small chance of failure (no result).
Approximate completeness is primarily of theoretical interest, as the time limits for finding solutions are usually too large to be of practical use.
Las Vegas algorithms have different criteria for the evaluation based on the problem setting.
Here, P(RT ≤ tmax), which is the probability of finding a solution within time, describes its run-time behavior.
With this data, we can easily get other criteria such as the mean run-time, standard deviation, median, percentiles, or success probabilities P(RT ≤ t) for arbitrary time-limits t. Las Vegas algorithms arise frequently in search problems.
If a value of pivot is either too big or small, the partition will be unbalanced, resulting in a poor runtime efficiency.
However, if the value of pivot is near the middle of the array, then the split will be reasonably well balanced, yielding a faster runtime.
The average of quicksort is computed over all possible random choices that the algorithm might make when choosing the pivot.
Note that the probability that the pivot is the middle value element each time is one out of n numbers, which is very rare.
[7] The complexity class of decision problems that have Las Vegas algorithms with expected polynomial runtime is ZPP.
This is the standard way to construct a Las Vegas algorithm that runs in expected polynomial time.
Note that in general there is no worst case upper bound on the run time of a Las Vegas algorithm.
In order to make a Las Vegas algorithm optimal, the expected run time should be minimized.
Furthermore, there is no point of running the experiment repeatedly to obtain the information about the distribution since most of the time, the answer is needed only once for any x.
By an application of Markov's inequality, we can set the bound on the probability that the Las Vegas algorithm would go over the fixed limit.
This can be done by running a Las Vegas algorithm for a specific period of time given by confidence parameter.