counting the number of inversions of a sequence in O(n \lg n) time
Counting inversions is equivalent to sorting. That's why it's 0(n log n). Any sorting algorithm can become an inversion counting algorithm by incrementing a counter instead of rearranging the input values. Inversions are the first topic in The Art of Computer Programming Chapter 5. Very much worth reading if you dig this stuff.
Counting inversions is equivalent to sorting. That's why it's 0(n log n). Any sorting algorithm can become an inversion counting algorithm by incrementing a counter instead of rearranging the input values. Inversions are the first topic in The Art of Computer Programming Chapter 5. Very much worth reading if you dig this stuff.