CODEWITHSUNDEEP
ccomplexity-theory
plaknas
plaknas

Reputation: 274

Elements in array O(nlogn) complexity method for finding pairs

Okay, I keep getting stuck with the complexity here. There is an array of elements, say A[n]. Need to find all pairs so that A[i]>A[j] and also i < j.

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

I did a merge sort in nlogn time and then a binary search for 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}

Irrespective of what I try, I keep getting another n^2 time in the complexity when I begin loops to compare. I mean, if I start for the first element i.e. 10, it is at index[2] which means there are 2 elements less than it. So if index[2]<index[i] then they can be accepted but that increases the complexity. Any thoughts? I don't want the code, just a hint in the right direction would be helpful.

Thanks. Everything i have been doing in C and time complexity is important here

Upvotes: 4

Views: 1603

Answers (2)

Klas Lindb&#228;ck
Klas Lindb&#228;ck

Reputation: 33273

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

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726559

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

Upvotes: 4

Related Questions