retagged by
20,527 views
66 votes
66 votes

In a permutation \(a_1 ... a_n\), of n distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\).

If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of \(1. . . n\)?

  1. \(\frac{n(n-1)}{2}\)
  2. \(\frac{n(n-1)}{4}\)
  3. \(\frac{n(n+1)}{4}\)
  4. \(2n[\log_2n]\)
retagged by

12 Answers

6 votes
6 votes

Expected number of inversion = $\frac{n(n-1)}{2}$

For randomly =>  $\frac{n(n-1)}{2}$ * 1/2 = $\frac{n(n-1)}{4}$

Answer: B

5 votes
5 votes
Best case - 0 inversions when the array is sorted

worst case - C(n,2) inversions (number of ways of choosing 2 elements from n elements as all of them can be inversions when the array is reverse sorted )

average case = [0 + C(n,2)] / 2 = n(n-1)/4
3 votes
3 votes

61.Take n=3,

Permutation ----> no of inversions

1 2 3                        0

1 3 2                        1

2 3 1                         2

2 1 3                         1

3 1 2                         2

3 2 1                         3

Total inversions =9, no of permutation =6,

So, here n=6

putting it in option n(n-1)/4=6⨉5/4=7.5

So, (B) is most closer option

62. Now elements are comes like 5,4,3,2,1

So,  first 5 comes order is 5--------------0 inversion

 Now, 4 comes........"       " 5,4 -----------1 inversion

 Now 3 comes..........."       " 4,5,3--------2 inversions

Now 2      "..........................3,4,5,2--------3  inversions

Now 1     " .......................2,3,4,5,1---------4 inversions

total 10 inversion

No more permutation could be done in insertion sort

So, number of permutation could be n(n-1)/2= O(n2)

Ans (A) here

0 votes
0 votes
Select 2 out of n and half of them will be inversions B.
Answer:

Related questions

1 votes
1 votes
1 answer
3
rsansiya111 asked Dec 7, 2021
315 views
In an array A[1..n] of n distinct elements, if i < j and A[i] A[j], then the pair (i,j) is called an inversion of A.How many inversions are there in the array A = {n,n-1...