Consider the following algorithm which takes as input a

Question

Question: Consider the following algorithm, which takes as input a sequence of n integers a₁, a₂,...,a_n and produces as output a matrix M = {m_ij } where m_ij is the minimum term in the sequence of integers a_i, a_i+1,...,a_j for j ≥ i and m_ij = 0 otherwise.

procedure bit count (S: bit string)
count := 0
while S ≠ 0
count := count + 1
S := S Λ (S - 1)
return count {count is the number of 1s in S}

a) Show that this algorithm uses O(n³) comparisons to compute the matrix M.

b) Show that this algorithm uses (n³) comparisons to compute the matrix M. Using this fact and part (a), conclude that the algorithms uses (n³) comparisons.

[Hint: Only consider the cases where i ≤ n/4 and j ≥ 3n/4 in the two outer loops in the algorithm.]