Suppose we are given a bit-vector A = A[1]... A[n] of length n (where A[i] is either 0 or 1). We wish to determine if at least half the elements in A are ls. Consider the following algorithm: HALFONES( A ) numOnes + 0 numZeros + 0 for i=1 to n do if A[i] = 1 then numOnes + + if numOnes > n/2 then return true else numZeros + + if numZeros > n/2 then return false Measure the complexity by counting the number of array comparisons performed. 1. (5 marks) What is the best case complexity of HALFONES? Do not use asymptotic notation. Justify your answer. 2. (5 marks) What is the worst case complexity of HALFONES? Do not use asymptotic notation. Justify your answer. 3. (15 marks) What is the average case complexity of HALFONES, assuming a uniform distribu- tion? Do not use asymptotic notation. Justify your answer. Remember to formally define the sample space, the probability distribution function, and any necessary random variables, as described in class. You do not need to mathematically simplify your