Problem $2.(30$ marks$)$

Consider this alogrithm:

$```$

$//$ pre: array A of length n$,$ each A$[$i$]$ is picked randomly uniformly

$//$ from the set $\{0,1,2,3,4,5,6,7,8,9\}.$

$//$ post: return the index of the first occurrence of "check digit" of A

$//($already computed in the code$)$

$//$ return $-1$ if check digit is not found

int FindCheckDigit$($A$)\{$

check$\_$digit $=0$

for $($i$=0$; i $$ n; i$++)$

check$\_$digit $=$ check$\_$digit $+$ A$[$i$]$

check$\_$digit $=$ check$\_$digit $\%10$ # $\%$ means remainder of division

for $($i $=0$; i $$ n; i$++)\{$

if $($A$[$i$]==$ check$\_$digit$)\{$

return i

$\}$

$\}$

return $-1$;

$\}$

$```$

Compute the average runtime for this algorithm. Show all details of your computation for both loops.