Las Vegas algorithm facts for kids
A Las Vegas algorithm is an algorithm that uses randomness which has the consequence that the algorithm terminates with probability $p<1$. If the algorithm does terminate then it does so with a correct result (unlike a Monte Carlo algorithm which definitely terminates but with a result that is only correct with probability $p<1$). The algorithm gambles with the resources used. It may take a very long times to give back a result, or it may not give back a result at all.
A simple example would be a version of the Quicksort. Quicksort is used to quickly sort things (mostly numbers). For this, each element is compared to a central element (called pivot). Depending on how this element is selected the sorting can take more time or less.
Most often, a Las Vegas algorithm is used to pick the pivot randomly.
See also
In Spanish: Algoritmo de Las Vegas para niños
