ME FT test: Algorithms

Question

Let an array A has n elements, where each element is a natural number. it is known that the array A has exactly r number of inversions. now every element int he array is made negative. then the time complexity of the most efficient algorithms which computes the inversion pairs in the modified array A will be?

 

Given answer: O(1)

My answer: O(n logn), because they have asked the inversion pairs, not the number of inversions. had they been asked the number of inversions, answer would be O(1).

please give your approach, and what do you think answer should be?

Comments

i think they ask about number of inversion pairs then we simply get in O(1).

$total-r\implies\frac{n(n-1)}{2}-r$

---

@Verma Ashish

please see the doubt i have underlined...

they have asked about inversion pairs... not the number of inversion pairs..

i think answer should be O(n logn )

in case of number of inversion pairs, answer would be O(1)