0 votes 0 votes 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 Algorithms algorithms sorting + – Akash Mishra asked Nov 22, 2017 Akash Mishra 748 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply joshi_nitish commented Nov 22, 2017 reply Follow Share 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. 3 votes 3 votes Akash Mishra commented Nov 22, 2017 reply Follow Share That is the correct answer. Thank You! 0 votes 0 votes akshat sharma commented Jan 2, 2018 reply Follow Share 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 0 votes 0 votes Please log in or register to add a comment.