I came across a question: Prove that any sorting algorithm that only compares and swaps contiguous values has a cost (worst case) $Ω(n^2)$
The question tries to be based on the fact that we do $\frac{n \times (n-1)}{2}$ inversions in the worst case, but that can't say anything about $Ω$ time complexity, can it?
The way the answer goes is max values are n * (n - 1) / 2. So, in the worst case, given the we fix one inversion per one swap, the sorting is $Ω(n^2)$
Then the solution says, and then since these sorting algorithms have $O(n^2)$ and $Ω(n^2)$ then they are $\theta(n^2)$. I don't get this reasoning when the above $Ω$ was calculated in a strange way.