Question 9639 – Sorting

In a permutation a₁…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 ?

Correct Answer: B

Question 8 Explanation:

Probability of inverse (a_i, a_j(i<j) =="" n(n-1)="" 2
Probability of expected no. of inversions = (1/2) × (n(n-1)/2) = n(n-1)/4

n(n-1)/2

n(n-1)/4

n(n+1)/4

2n[log₂n]