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.