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?

  • 2
    $\begingroup$ Are you missing something? Only one little detail - that you found the answer. n (n - 1) is in Ω (n^2). $\endgroup$
    – gnasher729
    Nov 30 '16 at 0:26
  • $\begingroup$ 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. $\endgroup$
    – Tyg13
    Nov 30 '16 at 0:30
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Nov 30 '16 at 0:38
  • $\begingroup$ @Tyg13 $f=\Omega(g) \Leftrightarrow g=O(f)$. $\endgroup$ Nov 30 '16 at 1:18
  • 3
    $\begingroup$ 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. $\endgroup$ 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.


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.