Question

Let A [1...n] be any 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 inversion in any permutation on n elements?

• A. $⊝\left(n^2\right)$
• B. $⊝\left(n\right)$
• C. $⊝\left(logn\right)$
• D. $⊝\left(nlogn\right)$

Answer 1

The correct option is A $⊝\left(n^2\right)$

If array elements are in decreasing order then we get maximum number of inversions.

$\frac{n(n-1)}{4}=O\left(n^2\right)$