Question on Inversion and sorting

Question

The average number of inversions in an unsorted array of n elements is?

(Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j)

A.) n(n-1)/2

B.) n(n-1)/4

C.) n(n+1)/2

D.) n!/2

Comments

min -> 0 inversion

max -> n(n-1)/2 inversions

avg = (min+max)/2 = n(n-1)/4

but remember this is not absolute avg. , because we are ignoring lot of  values between max and min, finding absolute avg require lot of computation.

---

That is the correct answer. Thank You!

---

Adding little information Total inversion =(n-1)+(n-2)+(n-3)+......1

sum of n natural number =(n*(n-1))/2

avg >>n*(n-1)/4

for more information about proof refer thishttps://math.stackexchange.com/questions/905700/maximum-and-average-number-of-inversions-in-array-by-induction    

https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/insertion/pages/ar01s04s01.html