Formally-algorithm Repeat Pick a random a e {0,17. See how many clauses the assignment x a satisfies. Return a if it satisfies 7m/8 clauses. This is a Las Vegas algorithm: The running time is not fixed.It's a random variable. 口 When the algorithm terminates,it always gives a correct output. The complexity measure is the expected running time. 9Formally - algorithm ◼ Repeat Pick a random 𝑎 ∈ 0,1 𝑛 . See how many clauses the assignment 𝑥 = 𝑎 satisfies. Return 𝑎 if it satisfies ≥ 7𝑚/8 clauses. ◼ This is a Las Vegas algorithm: ❑ The running time is not fixed. It’s a random variable. ❑ When the algorithm terminates, it always gives a correct output. ❑ The complexity measure is the expected running time. 9