Chapter 3.3, Problem 12E

1. Consider the following algorithm, which takes as input a sequence ofnintegers $a_1$, $a_2$, ..., $a_n$and produces as output a matrix $\text{M}=\left\{m_{ij}\right\}$where is the minimum term in the sequence of integers a, $a_i$, $a_{i+1}$, ..., $a_j$for $j\ge i$and $m_{ij}=0$otherwise.

initializeMso that $m_{ij}=a_i$if $j\ge i$and $m_{ij}=0$otherwise

for $i:=1$to $n$

for $j=i+1$to $n$

for $k:=i+1$to $j$

   $m_{ij}:=\min \left(m_{ij},a_k\right)$

return $\text{M}=\left\{m_{ij}\right\}${ $m_{ij}$is the minimum term of $a_i$, $a_{i+1}$, ..., $a_j$}

1. Show that this algorithm uses $O\left(n^3\right)$comparisons to compute the matrixM.
2. Show that this algorithm uses $\Omega \left(n^3\right)$comparisons to compute the matrixM. Using this fact and part (a), conclude that the algorithms uses $\Theta \left(n^3\right)$comparisons. [Hint: Only consider the cases where $i\le n/4$and $j\ge 3n/4$in the two outer loops in the algorithm.]