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 modification to this algorithm as follows. Find$-$Index$-$

$2($A$[1$ : n$])$:

$$ For j $=1$ to n:

$$ Sample i in $\{1,...,$ n$\}$ uniformly at random and if A$[$i$]$ mod $5=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 $5=0$ and output it as the answer.

Again, we skip the proof of correctness of this algorithm.

$14$

$($d$)$ What is the worst$-$case running time of Find$-$Index$-2($A$[1$ : n$])?$ What about its worst$-$case

expected running time? Remember to prove your answer formally