1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Note that "faster than O(...)" is a meaningless phrase. $\endgroup$ – Raphael Apr 25 '17 at 16:07
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Apr 25 '17 at 16:09
  • $\begingroup$ I already answered this question once... $\endgroup$ – Yuval Filmus Apr 25 '17 at 17:18
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.