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

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-03-06T12:35:59.020Z
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.
Emil Jeřábek
CC BY-SA 3.0
2015-03-06T14:26:48.200Z
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$.
domotorp
CC BY-SA 3.0
2015-03-06T17:07:03.570Z
@EmilJeřábek: Yes, thank you. I proved this by counting number of inversions, but yours is much simpler.
Vsevolod Oparin
CC BY-SA 3.0
2015-03-06T17:08:23.637Z
@domotorp: I assumed that this was more or less obvious.
Vsevolod Oparin
CC BY-SA 3.0
2015-03-06T05:07:29.057Z
2015-03-06T05:15:30.420Z
2015-03-06T05:15:30.420Z
Vsevolod Oparin
<p>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. </p>

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

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

<ds.algorithms><lower-bounds>
Lower bounds for inversion counting in comparison model?
Ben Cousins
# Lower bounds for inversion counting in comparison model?

(Asked by: username_0 on 2015-03-05)

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.

**Tags:** ds.algorithms, lower-bounds

---

## 1 answers

### Answer by username_1 on 2015-03-06. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_2**: 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.  
> **username_3**: 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$.  
> **username_1**: @EmilJeřábek: Yes, thank you. I proved this by counting number of inversions, but yours is much simpler.  
> **username_1**: @domotorp: I assumed that this was more or less obvious.  

---

