2 votes 2 votes Assume that A be an array of 16 elements. What is the difference between maximum number of inversion and minimum number of inversion for the array with 16 elements? Algorithms algorithms test-series maximum-minimum array + – srestha asked Dec 22, 2016 retagged Dec 16, 2023 by Hira Thakur srestha 795 views answer comment Share Follow See 1 comment See all 1 1 comment reply Ankit Srivastava 7 commented Sep 6, 2017 reply Follow Share Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes Array with 16 distinct elements arranged in decreasing order, will have $\binom{16}{2}$ inversions. Array with all elements equal will have 0 inversions. Difference = $\binom{16}{2} = 120$. air1 answered Dec 22, 2016 selected Dec 22, 2016 by srestha air1 comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments vijaycs commented Dec 22, 2016 reply Follow Share Let's take an example - 1 , 2, 3, 4, 5 We have total 0 inversions here. right ?? And in this question[https://gateoverflow.in/43576/gate2003-62] We are already given that total no of inversions are O(n). As we can see that range of total inversions varies from 0 to n(n-1)/2, so they have assumed a list where total no of inversions are O(n). Like - n , 1, 2, 3, 4, 5, ......, (n-1). Check above list - total inversions = O(n). Is it clear now ?? 2 votes 2 votes Kapil commented Dec 22, 2016 reply Follow Share Because that is already sorted, hence no swappings will be there like the one happens in bubble sort and insertion sort. But here the thing is how to know that input is sorted and it has 0 inversions. We have to parse the whole array which takes $O(N)$ time and after parsing we know that array was sorted,i.e no inversions were there. Hence, Insertion Sort actual TC = $O(N + f(n))$ where f(n) = total inversions 2 votes 2 votes srestha commented Dec 22, 2016 reply Follow Share ok, good :) 0 votes 0 votes Please log in or register to add a comment.