data structure

Question

the number of inversions in (n,n-1,.........3,2,1)

is n(n-1)/2

how??????????????????/

Answer 1

for element n inversion would be...n-1,n-2,n-3,.....1 

for n-1  it would be n-2,n-3,n-4......1 and so on...

so total would be...

n-1+n-2+n-3+n-4+.....+1+0 =(n-1)(n-1+1)/2 ->n(n-1)/2

Answer 2

$Inversions:$

a[i] and a[j] form an inversion if a[i] > a[j] and i < j 

Hence  2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3)

I can prove the maximum and average number of inversions in an array easily, like so...

The max will be when the array is fully unsorted in which case the number of inversions would be 

(n−1)+(n−2)+(n−3)........(n-(n-1))

This gets simplified to $0.5(n-1)n  = \frac{(n*(n-1))}{2}$ (worst case)

For average case 

 Now the average number of inversions will just be halfway between the best and worst case scenario. The worst case scenario is 0.5(n−1)n and the best case scenario is 0 so the

average would be $0.25(n−1)n = \frac{(n*(n-1))}{4}$

If you want to proof it by induction you can take help from this source: https://math.stackexchange.com/questions/905700/maximum-and-average-number-of-inversions-in-array-by-induction