How many comparisons does the selection sort (see preamble to Exercise 41 in Section 3.1) use to sort n items? Use your answer to give a big-O estimate of the complexity of the selection sort in terms of number of comparisons for the selection sort.

Step 1</p>

In this problem, we are asked to write the number of comparisons used by the selection sort and then give a Big-O estimate of the complexity of the selection sort.

Step 2</p>

A selection sort contains 2 loops in its program each containing n searches.

The second loop is contained inside the first loop, thus each search in the first loop does n comparisons.

Therefore the total number of comparisons becomes .