In the worst case, the total number of comparisons for Insertion Sort is closest to:

n^2/2
  • n
  • n^2
  • n \log n

Insertion Sort's implementation is made up of two nested for loops.

The outer for loop is executed n-1 times.

The inner for loop is executed i times.

The total cost is the sum of i's for i goes from 1 to n.