Consider the following algorithm with the stated Pre-assertion.

algorithm B(M): // Pre: Array M is a 1-dimensional length-n array of bits (either 0 or 1). // Post:

p := 0 q := 0 for i := 1 to n loop if M[i] = 1 then p++ if p >= n/2 then return true else q++ if q > n/2 then return false

Assume that the complexity measure of the algorithm is based on the number of array-element comparisons (M [] = ) performed. (a) What does the code fragment compute and provide the corresponding post-assertion Post? (b) Identify the best-case scenario (identifying all inputs M that yield the best-case scenario) and the best-case complexity of algorithm B(M ). Do not use asymptotic notations, and justify your answer. (c) Identify the worst-case scenario (identifying all inputs M that yield the worst-case scenario) and the worst-case complexity of algorithm B(M ). Do not use asymptotic notations, and justify your answer.