For sorting an array of size n through insertion sort, the total number of comparison operations is (n + the number of inversions in the array). The total number of pairs in an array is n * (n - 1) / 2.
Therefore, the maximum number of inversions possible
= n * (n - 1) / 2 (when the array is reverse-sorted)
The minimum of inversions = 0 (when the array is sorted)
For a randomly arranged array, the average number of inversions
= the average of the maximum number of inversions and minimum number of inversions
= n * (n - 1) / 4
Therefore, the running time of insertion sort averages out to be quadratic, i.e., O(n2).