Assume that the complexity measure of the algorithm is based on the number of array-element comparisons...

  

Transcribed Image Text:

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. algorithm B(M): // Pre: Array M is a 1-dimensional length-n array of bits (either 0 or 1). // Post: p = 0 9 = 0 for i 1 to n loop if M[i] 1 then p++ if p >n/2 then return true else q++ if qn/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. algorithm B(M): // Pre: Array M is a 1-dimensional length-n array of bits (either 0 or 1). // Post: p = 0 9 = 0 for i 1 to n loop if M[i] 1 then p++ if p >n/2 then return true else q++ if qn/2 then return false