If I is the number of
inversions in an input array of n records,
then Insertion Sort will run in what time?
\Theta(n+I)\Theta(n - I)\Theta(I - n)\Theta(n)\Theta(n^2)\Theta(I)Insertion sort has to do n passes where it
compares at least once.
If the record for this pass has no remaining inversions, then it requires no work.
But if it does have inversions, it will need a swap for each such inversion.