4 ms·
//Las Vegas algorithm repeat: k = RandInt(n) if A[k] == 1, return k; //Monte Carlo algorithm repeat 300 times: k = Ra
by puddingnomeat 6y ago
//Las Vegas algorithm
repeat:
k = RandInt(n)
if A[k] == 1,
return k;
//Monte Carlo algorithm
repeat 300 times:
k = RandInt(n)
if A[k] == 1
return k
return "Failed"
(...) Therefore, unlike Las Vegas, Monte Carlo does not gamble with run-time but correctness.
Interesting!