The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
2.7k views

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 (69k points)
retagged by | 2.7k views
Please answer this question
plz someone explain 2nd question

9 Answers

+33 votes
Best answer

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

average 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 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 Veteran (15.8k 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).

+9 votes

.....

answered by Veteran (12.8k points)
+8 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 (829 points)
+4 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 Boss (6.1k points)
+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 (81.4k 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.
+1 vote
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 Boss (7.7k points)
0 votes
Select 2 out of n and half of them will be inversions B.
answered by Loyal (3.3k points)
0 votes

61. Option B is correct.

62. Option D is correct.

answered by Veteran (17.5k points)
0 votes
B is the Answer
answered by Veteran (23.9k points)
Answer:

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

33,687 questions
40,231 answers
114,269 comments
38,800 users