Problem 2. Suppose we have an array A[1 : n] which consists of numbers {1,...,n} written in some arbitrary order (this means that A is a permutation of the set {1,...,n}). Our goal in this problem is to design a very fast randomized algorithm that can find an index i in this array such that A[i] mod 3 = 0, i.e., A[i] is divisible by 3. For simplicity, in the following, we assume that n itself is a multiple of 3 and is at least 3 (so a correct answer always exist). So for instance, if n = 6 and the array is A = (2, 5, 4, 6, 3, 1], we want to output either of indices 4 or 5. Now, consider the following simple algorithm for this problem: Find-Index-1(A[1: n]): Let i =1. While A[i] mod 3 #0, sample i {1,...,n} uniformly at random. Output i. The proof of correctness of this algorithm is straightforward and we skip it in this question. (c) What is the expected worst-case running time of Find-Index-1(A[1 : n])? Remember to prove your answer formally. The problem with Find-Index-1 is that in the worst-case (and not in expectation), it may actually never terminate! For this reason, let us consider a simple variation of this algorithm as follows. Find-Index-2(A[i: n]): For j = 1 to n: Sample i {1,...,n} uniformly at random and if A[i] mod 3 = 0, output i and terminate; otherwise, continue. If the for-loop never terminated, go over the array A one element at a time to find an index i with A[i] mod 3 = 0 and output it as the answer. Again, we skip the proof of correctness of this algorithm. (d) What is the worst-case running time of Find-Index-2(A[i : n])? What about its expected worst-case running time? Remember to prove your answer formally