Time complexity of Insertion Sort of an array of n numbers, with additional information

Question

Let there be an array A of n numbers. Let's define an inversion: there are two indexes, i < j, such that A[i] > A[j]. If my array A has K inversions, what is the time complexity of sorting the array with insertion sort?

I understand that the less inversions we have, the closer our array is to its sorted array. If there was just one inversion, that means there are only 2 elements which are not sorted (if there was more, then we'd have more inversions). However, I'm not sure how to analyze the general case. I'd appreciate any tips.

Answer 1

The insertion code provided below also remarks its number of operations, the calculation is for the worst case in which the array A is completely opposite of the sort. All elements of array A need to be swapped in every case.

for ( i = 1 ; i < n ; i++ )                     // 1(initialization) + n(check)
{
     j = i;                                     // n-1(initialization)
     while ( ( j > 0 ) && ( A[j-1] > A[j] ) )   // 2(∑ᵢ₌₁^{n} i) - 1 (checks)
     {
          temp = A[j];                          // ∑ᵢ₌₁^{n-1} i (operation)
          A[j] = A[j-1];                        // ∑ᵢ₌₁^{n-1} i (operation)
          A[j-1] = temp;                        // ∑ᵢ₌₁^{n-1} i (operation)
          j = j – 1;                            // ∑ᵢ₌₁^{n-1} i (operation)
     }
}                                               // n-1(incrementation)

Noticed that ∑ᵢ₌₁^{n} i means the sum of the n natural numbers starting from 1.

∑ᵢ₌₁^{n} i = n(n+1)/2

Number of Operations (worst case)

= 1 + n + (n-1) + 2(n(n+1)/2) - 1 + 4(n(n-1)/2) + (n-1)

= 2n + n(n+1) - 1 + 2(n^2 - n) + n - 1

= 2n + n^2 + n - 1 + 2n^2 + n -1

= 3n^2 + 2n - 2

The number of operations for the worst case is f(n) = 3n^2 + 2n - 2. Generally, we consider of best case (array perfectly sorted), worst case, and average case ((worst + best) / 2).

Another way to analyze the complexity of the algorithm is asymptotic notation. In this case, the upper bound of f(n) = O(n^2).