Suppose that we are given an array A with n keys and k inver

Suppose that we are given an array A with n keys and k inversions. Here, an inversion is defined as a pair of entries that are out of order in the array. What is the running time of Insertion sort when it is used to sort A in Big Oh notation? Why?

Solution

Solution:

For each inversion body of inner loop is iterates only once in insertion sort.. At every i-th iteration, if A[1..i] has min versions with A[i], they are in A[il..i1] (because sorted elements are there before i). This means that the inner loop will run only l number of times. Because of this process new inversions are not introduced in the every outer loop iteration is resolved in exactly l iteration. Where l is the distance the element is \"pushed towards the front of the array\".

Thus, the running time is (n+k), where k is the number of inversions (n comes from the outer loop).