40. Selection Sort Complexity

• It is known that for a list of length n, selection sort makes exactly

  • n(n – 1) / 2

  key comparisons and exactly

  • 3(n – 1)

  item assignments.

• Therefore, if n = 1000, then to sort the list, selection sort makes 500,000 key comparisons and about 3000 item assignments.