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.

$15$

$$ 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.

$($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. $(8$ points$)$