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 &gt; 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 &lt; 1$ but $S[0] &gt; 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?
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.