1 Matching Annotations
  1. Jul 2019
    1. The maximum number of comparisons for an insertion sort is the sum of the first n−1n−1n-1 integers. Again, this is O(n2)O(n2)O(n^{2}). However, in the best case, only one comparison needs to be done on each pass. This would be the case for an already sorted list

      i.e. Comparisons of an array of 25 element ranges from 300 down to more than 25.