The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+34 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]\)
asked in Algorithms by Veteran (52k points)
retagged by | 4.3k views
Please answer this question
plz someone explain 2nd question

9 Answers

+53 votes
Best answer

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,

answered by Boss (15.9k points)
edited by
AND it would need EXACTLY n swaps. even though it is theta(n).
@Arjun Dont you think that probability of getting an inversion is 1/n^2 rather than 1/2 as given in Happy Mittal solution. Can u cLear this doubt.

Happy Mittal question no. 63 link given above.
n - 1 inversions possible if greatest element in 1st position and all other elements in sorted order.

Hence, for placing each element in the correct place, 1 swap will be required. That's why  $\Theta (n)$ seems like the correct option.
In the solution sample space is defined as whether array has some inversions or not. So probability 1/2 and number of total inversions if have is n(n-1)/2
you are right, it will take n(n-1)/2 inversions for second anserr.

@Arjun please confirm

In solution to second question.

The array 1,2,3,7,5,4 will have three inversions rather than two. Isn't it?

inversion pairs: (7,5), (7,4) & (5,4).

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?

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

+16 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).

answered by Junior (781 points)

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

+12 votes


answered by Boss (12.2k points)
Which book is this bro?
+5 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

answered by Active (3.4k points)
For randomly, why u multiplied it by 1/2 ? Explain this please !
+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

answered by Veteran (111k points)
For 62 did not get what you are doing. Question says there are at most $n$ inversions and in your example there are $\frac{n . (n-1)}{2}$ inversions. So, you are solving wrong.
at most 1 inversion in each time. right?

then 1 card picking 0 inversion

2nd card picking atmost 1inversion


nth card picking at most n inversion

So, adding all inversion 1+2+...+n =O(n^2)
That is for that particular input- but question says to consider inputs with at most $n$ inversions.
+3 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
answered by Loyal (7.3k points)
0 votes
Select 2 out of n and half of them will be inversions B.
answered by Active (3.3k points)
@anshu garu

How can we say that the answer is half of it plzz xplain
0 votes

61. Option B is correct.

62. Option D is correct.

answered by Boss (15.5k points)
0 votes
B is the Answer
answered by Boss (11.6k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,120 answers
71,035 users