Cormen Edition 3 Exercise 2.4 Question 2 (Page No. 42)

Question

What array with elements from the set $\{1,2,\dots n\}$ has the most inversions? How many does it have?

Answer 1

$i<j ; A[i] > A[j]$

If an array is already sorted then number of inversions would be ZERO.

Now if the array is  REVERSE SORTED/ORDER then only it will have maximum number of inversions

<n,n-1,n-2,........2,1> it'll have n+n-1+n-2+...+1 = n(n-1)/2 inversions.

For example:

$\left \langle 8,6,3,2,1 \right \rangle$ now #inversions for this case are 10as following:

$(8,6) (8,3) (8,2) (8,1) (6,3) (6,2) (6,1) (3,2) (3,1) (2,1)$

Comments

please check for your formula for sum of n natural numbers