The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- \(\frac{n(n-1)}{2}\)
- \(\frac{n(n-1)}{4}\)
- \(\frac{n(n+1)}{4}\)
- \(2n[\log_2n]\)

+43 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,**

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.

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.

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

+13 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(n^{2}).

+1

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 ^{2} 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.

+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

+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(n^{2})

Ans (A) here

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

+2 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

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

0 votes

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,871 questions

47,531 answers

146,040 comments

62,297 users