Suppose you are applying insertion sort on an array. How will you relate its running time with the number of inversions?
An inversion in an array a[ ] is a pair of entries a[i] and a[j] such that i < j and a[i] > a[j] . The number of inversions w.r.t the current element, a[i] , is \( c_i-1 \), at each iteration, where \( c_i \) is the number of comparisons. If the total number of inversions ( Counting Inversions problem ) is \( N_i \), running time of insertion sort is \( O(n+N_i) \). |