6
$\begingroup$

For counting the number of inversions in an array, there are many $O(n \log n)$ algorithms, e.g. the one that modifies Merge Sort. There is an easy $\Omega(n)$ lower bound simply because you have to look at all the elements.

I saw some faster algorithms in the RAM model, such as this $O(n \sqrt{\log n})$ algorithm for a permutation on $n$ elements: http://people.csail.mit.edu/mip/papers/invs/paper.pdf.

Is anything else known in the comparison model for inversion counting? I'm mainly curious if there are better lower bounds.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

I'm not totally sure, but it seems you can get $\Omega(n \log n)$ lower bound.

Suppose in the worst case we use $o(n \log n)$ queries. Consider a decision tree for our algorithm. Cause of depth of the tree there should be a leaf such that there are at least two permutations which correspond to it.

Now consider all queries with answers on a path from the root to the leaf. We know that they set a partial, not total, order. Consider two elements, which can not be compared. Take any permutation, which corresponds to this order, and swap these elements.

I don't have a strict proof, but it seems to be true, that after such a swap number of inversions should be changed. If so, we broke our algorithm and obtained lower bound.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ The parity of the number of inversions is the sign of the permutation that brings to array to sorted form. The sign of a permutation is also the parity of the length of (some/every) expression of the permutation as a product of transpositions. So, yes, a single swap changes the parity of the number of inversions, and a fortiori the number itself. $\endgroup$
    – Emil Jeřábek
    Commented Mar 6, 2015 at 12:35
  • $\begingroup$ You are using (without explicitly stating) that in any partial order for any two incomparable elements, $x$ and $y$, there are two possible extensions that differ only in $x$ and $y$ being swapped. This is indeed true; If every element smaller than $x$ or $y$ is smaller than them, every other element bigger, then we can swap $x$ and $y$. $\endgroup$
    – domotorp
    Commented Mar 6, 2015 at 14:26
  • $\begingroup$ @EmilJeřábek: Yes, thank you. I proved this by counting number of inversions, but yours is much simpler. $\endgroup$
    – Vsevolod Oparin
    Commented Mar 6, 2015 at 17:07
  • $\begingroup$ @domotorp: I assumed that this was more or less obvious. $\endgroup$
    – Vsevolod Oparin
    Commented Mar 6, 2015 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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