Let A[1…n] be an array of n distinct numbers. If i < j and A[i] > A[j], then…
2016
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 ?
- A.
θ(n)
- B.
θ(lg n)
- C.
θ(n lg n)
- D.
θ(n2)
Attempted by 152 students.
Show answer & explanation
Correct answer: D
Answer: Θ(n^2).
Explanation: Use indicator variables for each pair of positions.
Define X to be the total number of inversions.
For each pair i < j, let X_{i,j} be 1 if A[i] > A[j] and 0 otherwise. Since all permutations are equally likely, P(A[i] > A[j]) = 1/2, so E[X_{i,j}] = 1/2.
By linearity of expectation, E[X] = sum_{i<j} E[X_{i,j}] = (number of pairs) * 1/2 = C(n,2)/2 = n(n-1)/4.
Therefore the expected number of inversions is n(n-1)/4, which is Θ(n^2).