arraysalgorithmmathdata-structuresinversion

in array A, we have an inversion (i, j). why do we have at least j-i inversions in array?

we have an array A that : in array A exist a pair (i, j) that i<j and A[i]>A[j]. why do we have at least j-i inversions in array A?

Solution

  • (i, j) is one inversion. The other j-i-1 involve the indices k such that i<k<j, since either A[i]>A[k] or A[k]>A[j] (otherwise, A[i]<=A[k]<=A[k], which implies A[i]<=A[j] and contradicts the assumption that A[i]>A[j]).