The following algorithm, Find01, takes as input a binary string of length n 2 whose bits are b1, b2, . . . , bn that starts with 0 and ends with 1. This algorithm returns a position i such that bi = 0 and bi+1 = 1. Find01(b1, b2, . . . , bn : binary string of length n 2 with b1 = 0 and bn = 1)

The following algorithm, Find01, takes as input a binary string of length n > 2 whose bits are b1, b2, ...,bn that starts with 0 and ends with 1. This algorithm returns a position i such that b = 0 and bi+1 = 1. Findo1 (b1, b2, ...,bn : binary string of length n > 2 with bi = 0 and bn = 1) 1. if n = 2 then 2. return 1 3. mid := (n/2) 4. if bmid = 0 and bmid+1 =1 then 5. return mid 6. else if bmid = 1 and &mid+1 =1 then 7. return Findo1(b1,...,bmid) 8. else 9. return mid + Findo1(6mid+1,...,bn) (a) (6 points) Prove that Find01 is correct. (b) (1 point) Give an example of a best-case input of size n = 6. Explain why this is a best-case input. (c) (1 point) What is the order of the algorithm in O notation, in the best case? Show how you get to your answer, using any valid method. (d) (1 point) Give an example of a worst-case input of size n = 6. Explain why this is a worst-case input. (e) (1 point) What is the order of the algorithm in O notation, in the worst case? Show how you get to your answer, using any valid method