Las Vegas to Monte Carlo Las Vegas:running time is B(x): random,always correct. run A(x)for 2T(n)steps; if A(x)returned ●A:Las Vegas Alg with return A(x); worst-case expected running time T(n). else return "yes" one-sided error! ● Monte Carlo:running time is fixed,correctness Pr[error] is random. ≤Pr[T(A(x)>2T(n)] ●B:Monte Carlo Alg E[T(A(x))] 1 ≤ ≤ 2T(n) -2Las Vegas to Monte Carlo • Las Vegas: running time is random, always correct. • A: Las Vegas Alg with worst-case expected running time T(n). • Monte Carlo: running time is fixed, correctness is random. • B: Monte Carlo Alg ... B(x): run A(x) for 2T(n) steps; if A(x) returned return A(x); else return “yes”; one-sided error! Pr[error] ￾ Pr[T (A(x)) > 2T (n)] ￾ E[T (A(x))] 2T (n) ￾ 1 2