Consider the algorithm Alg$1$ described below in pseudo$-$code. Alg$1$ takes as input an array $($whose elements are either $0$ or $1)$ and an integer $($the size of the array$).$ The index of the first element of the array is $1.$

Alg$1(A,n)$

$2.$

num$1$ larr$0$

num $0$larr$0$

ilarr$1$

$6.$

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

$1.$ State the best$-$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$).$

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

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