I'm having difficulties with analyzing the worst-case runtime of this following case:

I'm given an array that has $n$ natural numbers. Out of all $\binom{n}{2} = \frac{n(n-1)}{2}$ possible pairs there are $\frac{n(n-1)}{2} - 5n$ inversions. Inversion is defined like this: $a[i] < a[j],\ i>j$.

So of course you can sort the array in $O(n \log n)$ time but can you do any better than this? I've looked online and saw that inversion sort time is in $\Theta(n+I)$ where $I= \text{# inversions}$ but then I get that $I=\Theta(n^2)$ so it doesn't really help me.


Hint: Make use of the following facts:

  • Each pair $i,j$ that forms an inversion for sorting in ascending order, does not form an inversion when sorting in descending order (and vice versa).
  • Reversing the complete list can be done in $\Theta(n)$.
| cite | improve this answer | |
  • $\begingroup$ thank you very much I actually figured that out a few minutes ago. $\endgroup$ – Jake Keen Jul 10 '14 at 9:55

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.