No replies to this topic

[ductiletoaster]

Suppose we exchange elements a[i] and a[j] (j>i) which were originally out of order. For example if a= [2,8,3,7,1,5,6] and if we exchange second (i=2) and sixth (j=6) elements, we have [2,5,3,7,1,8,6] and now 5 and 8 are ordered and therefore the array has fewer inversions, i.e. several inversions are removed. In terms of i and j, what is the maximum number of inversions that can be removed if we exchange elements a[i] and a[j] ?

My prof had this on and old hw assignment and I was quite sure how to solve it and we have a test coming up so any help would be amazing