igate Test Series

Question

Rahul knows the implementation of merge sort. One day, his teacher asked him to find numbers of inversion in an array. An inversion can be defined in an array as if i < j, a[i] > a[j] then it is an inversion. Now, given there are p inversions in an array, if we multiply all elements by -1, what is the time complexity to find inversions in an updated array?

• O(n)
• O(nlogn)
• O(n^2)
• None
   

Answer 1

Since the question directly mentions the sorting algorithm name that is merge sort and we can use a modified merge sort that returns the number of inversions of an array A[1 ∶ N] in O(N log N) time.

Reference. → Cormen(3rd ed.), Chap-2, Page no-42

The key idea is to use the array index to find the number of inversions(as we know that while finding inversions two things (1: i < j, 2: A[i] >A[j] ) are of prime importance.)

we use the fact that if we replace an element by its position in the same sorted array, the inverse count will remain the same. The fact holds that the number of elements greater than a[i] for some i remains the same on the left of i. The inversion count will also thus stay the same.

Suppose we have an unsorted array(A) of negative numbers then we can copy the values from this original array to a new array(B) and perform a sorting operation on this new array.

Now search the position of all the elements of array A using binary search in B. Make the newly found position the new value of A[i]. And now we can easily check the number of inversions in the updated array A and the number of inversions will be equal to P.

Reference. ->Count Inversions (Approach 2)

For example – The array is represented as [Array values: Index]. Assuming the index is started from 1 for this example, Suppose the array was [2:1, 4:2, 6:3, 1:4, 5:5]  and is having 4 inversions and now we multiply (-1) by all the values of the array and the array A becomes [-2:1, -4:2,  -6:3, -1:4, -5:5]

Copying the values of array A to B and then sorting it so array B will become [-1:1, -2:2, -4:3, -5:4, -6:5]

And we can now see that ‘-1’ is having an index of ‘1’ and previously it was having an index of ‘4’. So we will save the newly found positions in array A on their respective locations with regards to their values stored in array A and array A will become [2:1, 3:2, 5:3, 1:4, 4:5 ] and now we will count the number of inversions and it will eventually be equal to 4. 

So T.C. will O(n log n), and option B will be the answer.

Note – we can also use Bucket sort to sort negative numbers and in order to reduce the time of bucket sort( as the worst case of bucket sort is O(n*n)) we can sort each bucket using merge sort, which will take O(n log n).

 

Answer 2

is it O(n)?

because if we multiply all elements of an array by (-1)  then the inequalities will also change

for eg.  we have an array like  |5|4|3|2|1|   here the number of inversions are 8.

after multiplying (-1) to all elements.

|-5|-4|-3|-2|-1|    

so now just one scan is enough to say that no inversion are there.

Comments

@Pranavpurkar

You are considering only Best Case.