GATE CSE 2003 | Question: 61

Question

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\)?

• A. \(\dfrac{n(n-1)}{2}\)
• B. \(\dfrac{n(n-1)}{4}\)
• C. \(\dfrac{n(n+1)}{4}\)
• D. \(2n[\log_2n]\)

Comments

thanks for sharing,it contains awesome questions

---

we want a[i]> a[j] while i<j

for a pair we need to choose NC2 elements , these are maximum elements where i<j

probability of each pair where a[i]>a[j] is 1/2

so ,

Expectation = 1/2 * nC2

---

Simplest Big brain approach - 

Take n = 2 
1,2 
1,2 = 0 inversion 
2,1 = 1 inversion 

E(2) = 1/2*1 = 1/2 

Put n=2 in all options 
match with 1/2 only Option B Matches 

Please try to understand other approaches also after understanding this. 

Answer 1

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.

Comments

Also the reason for summing these variables seemed arbritrary to me. For example, not every one of these inversions can happen at the same time (i.e. they are not independent) so why are we simply summing them?

If we imagine these random variables as a collective probability then we can draw a specific sample from this distribution (1 for inversion present, 0 for absent). The total inversions in the permutation is the sum of these 1s.

So after reading this, I can see that when each inversion has a random variable associated with it, the total inversions in the permutation is a sum of these random varibles (the sum will never equal $^nC_2$ but that’s a nature of the underlying probability distribution which we don’t care about).

Once we have this sum, we are free to calculate expectation as a linear sum and that allows us to calculate $\frac{^nC_2}{2}$.

---

this answer is very incorrect. It seems like people would try to justify the answer key’s answer by any means, even if it is wrong. I Have seen this on many other questions too.

---

bro are you blind or what its completely opposite of what u have said because even it is possible that answer key is wrong but here all sir's and even our seniors after analyzing only they will post answers.let's suppose even if one answer value may be wrong but concept will never wrong in this site and i learnt so much from this site so please i hope u understand

Answer 2

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,

Comments

For two inversions the array can be - 1,2,3,7,5,6.

---

isnt expectation different from average...are we not taking care of probabilities?

---

@Vamsi krishna satya I am also taking a small example of 3  elements (1,2,3) but getting expectation as (4/3)

Answer 3

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(n²).

Comments

for b) part ....take the example 6 5 4 3 2 1....which is one of the permutation of 1...n (n=6 here) 

element 6 takes 5 inversions , 5 having 4, 4 taking 3.....2 taking 1 = 5+4+3+2+1 = sum of n-1 numbers = n² inversions. (but atmost 'n' inversions allowed)

So, worst case is to have case like 6,1,2,3,4,5 having only O(n) inversions. 

So such almost sorted array in insertion sort requires O(n) time (best case of Insertion Sort). So ans should be D.

---

In (3, 2, 1) there should be 1 inversion rather than 3 because question is not asking about inversion takes place b/w adjacent element only. Correct me if I wrong.

Answer 4

.....

Comments

Which book is this bro?

Answer 5

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

Comments

For randomly, why u multiplied it by 1/2 ? Explain this please !

---

every pair has probability to be a inversion or not be a inversion  there are two chances and for all those combinations it has probability of ½ to be a inversion pair so we will multiply each pair with ½

Answer 6

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

Comments

Since the number of inversions are ranging from 0 to C(n,2) (i.e, 0 ,1, 2, …., C(n,2) )… this approach works ,

but if at all the problem is like to calculated No of something ,  for example is not sequential ,

like 0 , 5 , 30 , …,C(n,2),( just random numbers given ).

 

Then your approach doesn’t work , So Arjun Sir has answered above as a general approach.

Anyways no problem , Good answer !