search
Log In
53 votes
9.6k 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]\)
in Algorithms
retagged by
9.6k views
0
Please answer this question
0
plz someone explain 2nd question
0
thanks for sharing,it contains awesome questions

11 Answers

0 votes

Ans -B 

Let \(X_{ij}\) be an indicator random variable s.t. $$X_{ij} = \begin{cases} 0 &\mbox{if } (a_i,a_j) \text {not inverted} \\ 1 & \mbox{if } otherwise. \end{cases}$$ Let random variable \(X\) denotes total number of inversions. So clearly \(X=\sum\limits_{\substack{i,j \\ i<j}}X_{ij}\). Note that their are \(^n\mathrm{C}_2\) terms in summation, because there are total \(^n\mathrm{C}_2\) pairs, and each pair is either inverted or not.
So now we want to find \(E(X)\). Now \(E(X)=\sum\limits_{\substack{i,j \\ i<j}}E(X_{ij})\). But \(E(X_{ij}) = \frac{1}{2}\), because for any pair, probability of inversion is same as of not inversion.
So \(E(X) = \frac{^n\mathrm{C}_2}{2} = \frac{n(n-1)}{4}\).
So option (B) is correct.

ago
Answer:

Related questions

56 votes
9 answers
1
11.6k 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\). What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of \(1. . . n\) with at most $n$ inversions? \(\Theta(n^2)\) \(\Theta(n\log n)\) \(\Theta(n^{1.5})\) \(\Theta(n)\)
asked Apr 24, 2016 in Algorithms jothee 11.6k views
43 votes
2 answers
2
8.9k views
The unusual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will remain $\Theta(n^2)$ become $\Theta(n (\log n)^2)$ become $\Theta(n \log n)$ become $\Theta(n)$
asked Sep 16, 2014 in Algorithms Kathleen 8.9k views
42 votes
7 answers
3
6.6k views
In the following $C$ program fragment, $j$, $k$, $n$ and TwoLog_n are integer variables, and $A$ is an array of integers. The variable $n$ is initialized to an integer $\geqslant 3$, and TwoLog_n is initialized to the value of $2^*\lceil \log_2(n) \rceil$ for (k = 3; k <= n; k++) A[k] ... $\left\{m \mid m \leq n, \text{m is prime} \right\}$ { }
asked Sep 17, 2014 in Algorithms Kathleen 6.6k views
43 votes
4 answers
4
9.6k views
Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in which no vertex ... longest path length from $j$ to $k$ If there exists a path from $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges
asked Sep 17, 2014 in Algorithms Kathleen 9.6k views
...