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]$
retagged | 2.7k views
plz someone explain 2nd question

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

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.

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

.....

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

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

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

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

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
Select 2 out of n and half of them will be inversions B.

61. Option B is correct.

62. Option D is correct.