# Find a sequence of $n$ integers with $\Omega(n^2)$ inversions

So right off the bat, this is in fact a homework question. I've been banging my head on this problem for hours. From my naive understanding of inversions, I feel that this is not possible.

Considering for $n=1$ elements, there are no inversions, it already seems like this won't work, but maybe it's just for $n > 1$, so we try $n = 2$. And the best I can seem to get is $1$ inversion, where the set is $\{2,1\}$, thus there is one inversion, since $0 < 1$ but $S[0] > S[1]$. The best I can seem to get is $\{n, n-1, \dots, 2, 1\}$, where there are $n(n-1) - 1$ inversions.

Am I missing something in my approach?

• Are you missing something? Only one little detail - that you found the answer. n (n - 1) is in Ω (n^2). – gnasher729 Nov 30 '16 at 0:26
• Isn't $n^2 - n < n^2$ and thus not in $\Omega(n^2)$? Maybe I'm missing something about $\Omega$, but I thought that was minimum. – Tyg13 Nov 30 '16 at 0:30
• Find the definition of Ω (n^2) and read it carefully. It means anything between c1·n^2 and c2·n^2, for some 0 < c1 < c2, for all large n. – gnasher729 Nov 30 '16 at 0:38
• @Tyg13 $f=\Omega(g) \Leftrightarrow g=O(f)$. – David Richerby Nov 30 '16 at 1:18
• I'm voting to close this question because it seems the asker already knows the answer, except that they misunderstood $\Omega$-notation. As such, there's nothing left to answer. – David Richerby Nov 30 '16 at 1:21

Sorta answered my own question in the comments, so I decided to put this here:

If we take any sequence of $n$ integers, in reverse order like $\{n,n-1,\dots, 2, 1\}$. Then each digit $S[i]$ will have $(i-1)$ inversions, and there are $n$ digits.

Thus $I(n) = \displaystyle\sum_{0}^{n-1} n = 0 + 1 + 2 + \dots + (n-1)$. So the total number of inversions will be $I(n) = \dfrac{n(n-1)}{2}$.

Then see, since $n^2 = O\left(\dfrac{n(n-1)}{2}\right)$, $\dfrac{n(n-1)}{2} = \Omega(n^2)$.

Thus $I(n) \in \Omega(n^2)$, and we have a sequence of $n$ digits with $\Omega(n^2)$ inversions.

A random permutation will work.

Let $\pi \in S_n$ be a uniformly random permutation. For $i < j$, denote by $E_{ij}$ the event that $\pi(i) > \pi(j)$, let $X_{ij}$ be the corresponding indicator variable, and let $X=\sum_{i<j} X_{ij}$ be the number of inversions. Since $\Pr[E_{ij}] = 1/2$, linearity of expectation shows that the expected number of inversions is $$\mathbb E[X] = \frac{1}{2} \binom{n}{2} = \Omega(n^2).$$

With a bit more work, we can also compute the variance. If $\{i,j\} \cap \{k,\ell\} = \emptyset$ then $$\Pr[E_{ij} \land E_{k\ell}] = \frac{1}{4}.$$ If $i < j < k$ then $$\Pr[E_{ij} \land E_{jk}] = \frac{1}{6}, \qquad \Pr[E_{ik} \land E_{jk}] = \Pr[E_{ij} \land E_{ik}] = \frac{1}{3}.$$ This shows that $$\mathbb E[(X_{ij}-1/2)^2] = \frac{1}{4} \\ \mathbb E[(X_{ij}-1/2)(X_{k\ell}-1/2)] = 0 \\ \mathbb E[(X_{ij}-1/2)(X_{jk}-1/2)] = -\frac{1}{12} \\ \mathbb E[(X_{ij}-1/2)(X_{ik}-1/2)] = \mathbb E[(X_{ik}-1/2)(X_{jk}-1/2)] = \frac{1}{12}$$

Therefore $$\mathbb V[X] = \frac{1}{4} \binom{n}{2} + \frac{1}{6} \binom{n}{3} = O(n^3).$$ Chebyshev's inequality then shows that $$\Pr\left[X < \frac{1}{4}\binom{n}{2}\right] \leq \frac{\mathbb V[X]}{\frac{1}{16} \binom{n}{2}^2} = O\left(\frac{1}{n}\right).$$ In other words, a random permutation will have $\Omega(n^2)$ inversions with high probability.