Have u tried BIT Approach
On Mon, Oct 22, 2012 at 1:40 AM, Aamir Khan syst3m.w...@gmail.com wrote:
What is the best algorithm to print all the inversions in an array? While
you can find the inversion count using modified merge sort procedure in
O(nlog(n)) time [1] but I doubt that
Since the number of inversions are of order n^2 in the worst case, so
should be the complexity of printing them apparently.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To
What is the best algorithm to print all the inversions in an array? While
you can find the inversion count using modified merge sort procedure in
O(nlog(n)) time [1] but I doubt that printing all inversions can also be
done in O(nlogn).
In an array A[], two elements A[i] and A[j] form an