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 thats not possible?
Can we count the number of inversions in time $\mathcal{O}(n)$?
complexity theory;asymptotics;lower bounds;permutations
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 Ptracu gave an $O(n\sqrt{\log n})$ algorithm in their 2010 paper Counting inversions, offline orthogonal range counting, and related problems. Chan and Ptracu 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.