Here is an example of a deterministic algorithm for the problem. if x[1] then if x[3] then return false else if x[2] then return true else return false else if x[2] then return true else if x[3] then return true else return false Note that for some inputs, the algorithm requires 3 looks, for others, 2. But the worst case cost is 3, such as if the input is 000. You need to prove that the worst case cost for every deterministic algorithm for the problem is 3. (There are really quite a large number of these algorithms, so listing every one of them and giving the worst case for each is NOT the way to go.)