Alg$1(A,n)$

$2.$

$3.$ num $1$larr$0$

$4.$ num $0$larr$0$

$5.$ ilarr$1$

$6.$

$7.$ while $in$ do

if $A[i]=1$ then

num$1$ larr num $1+1$

if num$1\frac{n}{2}$ then

return TRUE

endif

else

num $0$larr num $0+1$

if num $0>\frac{n}{2}$ then

return FALSE

endif

endif

ilarri$+1$

endfor

When estimating the run$-$time complexity of Alg$1$ as a function of the size of the input array consider only the number of array comparisons performed when the algorithm is run on the input array. $($Note that array comparisons only occur on line $8$ of Alg$1.)$

$(5$ marks$)$ State the worst$-$case running time complexity of Alg$1$ as a function of the size of the input array. Do not use the asymptotic notation. Explain your answer $($show your calculations$).$

$(6$ marks$)$ State the average case complexity of Alg$1$ as a function of the size of the input array. Explain your answer using the methodology presented in class, i$.$e$.,$ define an appropriate sample space, state a probability distribution function $($assume a uniform distribution$),$ define the necessary random variables, etc. Show your calculations$\mathrm{.}8$