The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+29 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]\)

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

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

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.

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

+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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,269 comments

38,800 users