We are given BINARY list L of size n. Problem- count the amount of 0's in the list L. pseudo code given for this: (see the picture below)

a- what is run time of this algorithm? b- suppose that n = 10^6 and extactly 1/4 of all elements in L are 0, what is the probability that CountZeroes returns 0? c- in picture attached.

function COUNTZEROES(L) n length(L) count 0 for j 1 to 100 do Comment: pick a random index i between 1 and n i random(1, n) if L[i] = 0 then count count + 1 return n count/100 (a) What is the running time of this algorithm? Please show all your work. (b) Suppose that n106 and exactly a quarter of the elements in L are 0. What is the probability that the COUNTZeroes function returns 0? (c) A random variable X has binomial distribution with parameters m (a positive integer) and p (a real number between 0 and 1) if p. (1 -p) The way to think about X being binomially distributed is that we perform m indepen- dent random trials and each trial can either succeed or fail. The "success" probability of a trial is p and so the failure probability of a trial is 1 - variable X represents the number of successful trials, out of m total random trials To understand the formula in (1) note that the probability of k successful trials is p the probability of (m - k) unsuccessful trials is (1 - p)m-*, and there are (") ways of distributing the k successful trials among the m random trials As in (b) suppose that n 106 and exactly a quarter of the elements in L are 0. Using the above expression for a binomial distribution, write down the expression for the probability that CouNtZEROES returns the correct answer, namely 106/4 p. Then the random