October 23, 2023
October 23, 2023
October 23, 2023
###### Digital-Logic-Design
October 23, 2023
 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 θ(n2)
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(n2). 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 Θ(n2).

→ 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).

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(n2). 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 Θ(n2).

→ 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).