4 ms·
Counting Inversions via Rank Queries
- brudgers 7y agocounting 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.
- jbapple 7y agoDoes this apply to integer keys in the computational models that can do operations other than simple comparisons? In the transdichotomous model, I thought the best known sorting algorithms were O(n lg lg n) worst case, while the best known inversion counting models were Ω(n √ lg n), following “Counting Inversions, Offline Orthogonal Range Counting, and Related Problems”.
- brudgers 7y agoThanks. I didn't think about it. I was only thinking of the general case of sorting. Integer sorting seems like a case where there's meaningful metadata (maximum integer) and the algorithm is written only for that case (and assumes suitable hardware). These aren't radical assumptions and the optimization may have a lot of practical applications. But once I get to specify the inputs, then O(1) sorting is trivial. Specify the input as sorted lists. To me, it only seems a matter of degree. But admittedly, what can be represented as an integer is a much more reasonable degree of specification.