retagged by
20,539 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

Best answer
68 votes
68 votes

With $n$ integers we can have ${}^nC_2 = \frac{n(n-1)}{2}$ possible pairs. 

Now, since the integers are distinct, and selection is random if we take any pair, it is equally likely to be inverted or not. i.e., probability of inversion $ = 0.5.$

Now, since we have ${}^nC_2$ pairs and probability of each pair being inverted $ = 0.5$, expected number of inversions,

$E = \sum_{i=1}^{{}^nC_2} 0.5 = 0.5 \times\frac{n.(n-1)}{2} = \frac{n(n-1)}{4}.$

Correct Option: B.

58 votes
58 votes

They are asking the average number of inversion. basically what $i$ learned about averages from dbms indexing is.

Aaverage apart from the standard definition can be calculated as $( best \ case + worst \ case )/2 $

and inversion is like $ 9,5$.

So, best case will be sorted array $- 1,2,3,4,5$ no inversion .$ = zero$

$worst \ case = 9,5,4,3,2,1$ . here total number of inversion will be $n(n-1)/2$ as . $9$ can be paired with any $5$ elements $(5,4,3,2,1)$ will form a inversion pair. similarly $5$ with $4$.elements .

So, we can say if we have $n$ elements then. it will be $(n-1)+(n-2)+(n-3)...+2+1$ which is the sum of first $n-1$ natural numbers. So, it is $n(n-1)/2$

So, expected average number of inversion $= (n(n-1)/2 + zero (best \ case)) /2= n(n-1)/4$

So, option is B.

Second question.

we all know that insertion sort has complexity due to swapping and movements, if we have $n$ $n$ inversion pair then the movements and comparison will be restricted to $n$ only . like if inversion is $1$ , then array must be sorted and only the inversion should exist at the end, like $1,2,3,5,4$. otherwise more than one inversion pair will form. so to sort this. for two it will be $1,2,3,7,5,4$. so to sort this type of array using insertion sort atmost $N$ swaps wiill be required, so D,

edited by
39 votes
39 votes

If u dont have any proper method to solve , try by taking small example and eliminate options.

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 cases =6, expected no of inversions=9/6 = 1.5, put in all options , only B satisfied.

62) We have seen maximum n inversions can occur. So no use of restriction , and 3 2 1 in this case Insertion sort will take o(n2).

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...