NIST

Las Vegas algorithm

(algorithmic technique)

Definition: A randomized algorithm that always produces correct results, with the only variation from one run to another being its running time.

Generalization (I am a kind of ...)
randomized algorithm.

Specialization (... is a kind of me.)
skip list insert, Quicksort variants that pick the pivot randomly, 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.

Author: CRC-A


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 28 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

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. 28 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/lasVegas.html