Let A1nl be an array of n distinct numbers i j is called an

Let A[1..nl be an array of n distinct numbers (i, j) is called an inversion of A if i A[j]. The inversion number of A, denoted by inversion(A), is the total number of inversions of array A. Express the running time of sorting A using insertion sort. Your answer should use asymptotic notations involving n and inversion(A). Justify your answer. List all the inversions of the following array Suppose you have an array A with n elements. Array B is obtained from array A by deleting two elements and inserting them back (to some positions) in array A. Find an upper-bound on inversion(A)-inversion (B)

Solution

1)It is the reversed array, that is n,n1,…,1. It has (n1)+(n2)++1=n(n1)2 inversions.

2)2,1, 3,1, 8,6, 8,1 and 6,1.