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$

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.