edited by
5,714 views
3 votes
3 votes

Let $A[1,...,n]$ be an array of n distinct numbers. If $i<j$ and $A[i]>A[j]$, then the pair $(i,j)$ is called an inversion of $A$. What is the expected number of inversions in any permutation on $n$ elements?

  1. $\theta(n)$
  2. $\theta(lgn)$
  3. $\theta(nlgn)$
  4. $\theta(n^2)$
edited by

3 Answers

0 votes
0 votes

We have to find Total Pairs in all permutation.

n distinct numbers

Number of Pairs, $N =\binom{n}{2} = \frac{n(n-1)}{2}$ (can be considered as size of the upper triangle of a square matrix)

event A: Inversion for a pair.

Probability ( Inversion for a pair) =  $P = P(A) = \frac{1}{2}$  (either there is inversion or there is not)

Similarly, $q = \frac{1}{2}$

Random Variable X: Number of Inversions

$X\sim B (N=\binom{n}{2}, P=\frac{1}{2})$

$E(X) = \mu = NP$

$= \binom{n}{2} . \frac{1}{2} = \frac{n(n-1)}{4}$

Complexity = $\theta (n^2)$

Similar Question – https://gateoverflow.in/949/gate2003-61

Answer:

Related questions

1 votes
1 votes
2 answers
2
1 votes
1 votes
2 answers
3
go_editor asked Aug 20, 2016
2,344 views
Match the following :$\begin{array}{clcl} \text{(a)} & \text{Huffman Code} & \text{(i)} & O(n^2) \\ \text{(b)} & \text{Optical Polygon Triangulation} & \text{(ii)} & \t...