Arrays

Question 52

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	θ(lgn)
C	θ(nlgn)
D	θ(n²)

ProgrammingArraysUGC NET CS 2016 July- paper-3

Question 52 Explanation:

→ Count of number of times the inner loop of insertion sort executes is actually equal to number of
inversions in input permutation a1,a2,…an. Since for each value of i=1..n, j take the value 1..i−1, which means for every j < i it checks if a [ j ] > a [ i ] .

→ In any given permutation, maximum number of inversions possible is n(n-1)/2 which is O(n²). It is the case where the array is sorted in reverse order.

→ To resolve all inversions i.e., worst case time complexity of insertion sort is Θ(n²).

→ However, as per the question the number of inversions in input array is restricted to n.

→ The worst case time complexity of insertion sort reduces to Θ(n).

Correct Answer: A