Elements in a complexity method with O (nlogn) set for finding pairs

Question

Well, I get hung up on difficulties all the time. There is an array of elements, for example A[n] . You need to find all the pairs so that A[i]>A[j] , as well as i < j .

So, if it's {10, 8, 6, 7, 11} , the pairs will be (10,8) (10, 6), (10,7) and so on...

I did a merge sort at nlogn time, and then binary search the entire array again in nlogn to get the indices of the elements in the sorted array.

So sortedArray={6 7 8 10 11} and index={3 2 0 1 4}

No matter what I try, I keep getting another n^2 time in complexity when I start comparing cycles. I mean, if I start the first element, i.e. 10, then it is equal to index[2] , which means that 2 elements less than it. Therefore, if index[2]<index[i] , then they can be accepted, but this increases complexity. Any thoughts? I don't need the code, just a hint in the right direction would be helpful.

Thanks. Everything I did in C and the complexity of the time is important here c

Answer 1

The result consists of elements O (n ^ 2), so any attempt to iterate over all pairs will be O (n ^ 2).

Answer 2

You cannot do this in O(N^2) , because the number of pairs that the algorithm will generate when the original array is sorted in descending order is N(N-1)/2 . You simply cannot get the results of O(N^2) in O(N*LogN) time.