Give an example of a sequence of n integers withΩ(n 2 ) inversions

Question

I'm working on a exercise but it's confusing to understand.

I assume that the worst case for a inversion is that there is a sequence that's sorted in descending order: [n,n-1,...,0] which has (n(n-1))/2 inversions. Then we have to prove that (n(n-1))/2 >= C · n^2 based on the definition of omega which is g(n) >= C · f(n). But when n goes to infinity, g(n) = 1/2, so there doesn't exist a constant C which C>=1 and n0 >= 1 that satisfy the inequality.

What am I missing?

Answer 1

I'm assuming that the question you are asked is, Give an example of a sequence of n integers with ?(n^2) inversions.

They worded this a bit sloppily. But here is what you need to come up with:

1. The rule for generating sequences.
2. A number 0 < n_0.
3. A constant 0 < C such that if n_0 < n then the number of inversions of the nth sequence is greater than C * n^2.

You've already given a rule that you think might work. n numbers sorted descending.

I would suggest that you try n_0 = 2 and C = 1/4.

Can you prove this statement?

If 2 < n, the descending sequence of length n has more than (1/4) * n^2 inversions.