randomized algorithm guaranteed to eventually produce correct or optimal results From Wikipedia, the free encyclopedia
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.