4.3k 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]$
retagged | 4.3k views
0
0
plz someone explain 2nd question
+9
0

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
0
AND it would need EXACTLY n swaps. even though it is theta(n).
0
@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.
0
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.
0
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
0
you are right, it will take n(n-1)/2 inversions for second anserr.

+1

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

0
For two inversions the array can be - 1,2,3,7,5,6.
0
isnt expectation different from average...are we not taking care of probabilities?
0

@ I am also taking a small example of 3  elements (1,2,3) but getting expectation as (4/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(n2).

answered by Junior (781 points)
+2

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.

.....

answered by Boss (12.2k points)
0
Which book is this bro?

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

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

answered by Active (3.4k points)
0
For randomly, why u multiplied it by 1/2 ? Explain this please !

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

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

61. Option B is correct.

62. Option D is correct.

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

1
2