Definition: A randomized algorithm that always produces correct results, with the only variation from one run to another being its running time.
Specialization (... is a kind of me.)
random search, Grover's algorithm, Czech, Havas, and Majewski's order-preserving minimal perfect hashing.
See also Monte Carlo algorithm, ZPP.
Note: From Algorithms and Theory of Computation Handbook, 15-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
A Monte Carlo algorithm gives more precise results the longer you run it. A Las Vegas algorithm always gives the right answer, but the run time is indeterminate.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 4 February 2009.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "Las Vegas algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 4 February 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/lasVegas.html