Las Vegas algorithm
randomized algorithm guaranteed to eventually produce correct or optimal results
Facts
10 properties- Instance of
- algorithmic paradigm
- Subclass of
- randomized algorithm, exact algorithm[4][5]
- Best-case time complexity
- O(n \log(n))
- Defining formula
- \textrm{ZPP} = \textrm{RP} \cap \,\text{co}\,\textrm{-RP}, \,\!
- Derivative work
- Davis–Putnam algorithm[8]
- Discoverer or inventor
- László Babai[2]
- Opposite of
- Monte Carlo algorithm[6]
- Time of discovery or invention
- 1979[7]
- Worst-case time complexity
- O(n^2)
🏷️ Also known as
en Las Vegas algorithm
ar خوارزمية لاس فيغاس
cs algoritmus typu Las Vegas
de Las-Vegas-Algorithmus
es algoritmo de Las Vegas
fa الگوریتم لاس وگاس
fr Algorithme de Las Vegas
he אלגוריתם לאס וגאס
ja ラスベガス法
ko 라스베이거스 알고리즘
ru Лас-Вегас
tr Las Vegas algoritması
zh 拉斯维加斯算法
🔖 Identifiers · 6
🔗 Connections
Derivative work 1
Discoverer or inventor 1
Examples 1
Maintained by WikiProject 1
Named after 1
Opposite of 1
Subclass of 1
← Opposite of 1
Press Enter · cited answer in seconds
0 sources
Summary
Las Vegas algorithm is an algorithmic paradigm[1].