# Can we count the number of inversions in time $\mathcal{O}(n)$?

It is possible to find the total number of inversions by $\mathcal{O}(n\log{}n)$ running time (extension of merge-sort algorithm for example).

Is there more asymptotically efficient way to do it? $\mathcal{O}(n)$? Or is there any proof that’s not possible?

• Note that "faster than O(...)" is a meaningless phrase.
– Raphael
Apr 25 '17 at 16:07
• Note also that there is lots of room between $\Theta(n \log n)$ and $O(n)$. Are you not interested in, say, an $\Theta(n \log(\log n))$ algorithm?
– Raphael
Apr 25 '17 at 16:09
• I already answered this question once... Apr 25 '17 at 17:18

There are $o(n\log n)$ algorithms in the RAM model. Dietz gave an $O(n\log n/\log\log n)$ algorithm in his 1989 paper Optimal algorithms for list indexing and subset rank, and Chan and Pătraşcu gave an $O(n\sqrt{\log n})$ algorithm in their 2010 paper Counting inversions, offline orthogonal range counting, and related problems. Chan and Pătraşcu also gave an $O(n)$ algorithm for finding a $1+\epsilon$ approximation, for any $\epsilon>0$.
If you only allow comparisons, then there is an $\Omega(n\log n)$ lower bound, see this question on cstheory.