0
$\begingroup$

There is given sequence $a_1,...a_n$ such that there are $O(n^{\frac{3}{2}}) $ inversions in this sequence. I am thinking about sorting algorithm for that.

I know lower bound for number of comparisons - it is $O(n)$ - on the contrary, there would be a minimum finding algorithm faster than $O(n)$.

Nevertheless, I don't have idea how sort it in linear time ? What doy you think ?

Inversion is a pair $(i, j)$ such that $i < j$ and $a_i > a_j$

Improve this question
$\endgroup$
4
  • $\begingroup$ What is an inversion? $\endgroup$
    – usul
    Oct 6, 2015 at 14:16
  • $\begingroup$ inversion is a pair $(i, j)$ such that $i < j$ and $a_i > a_j$ $\endgroup$
    – user40545
    Oct 6, 2015 at 14:17
  • $\begingroup$ Hmm, can you expand on the consequences of this $n^{\frac{3}{2}}$ upper bound? It seems like a large part of the sequence must already be sorted? $\endgroup$
    – usul
    Oct 6, 2015 at 15:38
  • $\begingroup$ Yes, intuiton is that large part is arleady sorted. However I don't know how to use this fact. $\endgroup$
    – user40545
    Oct 6, 2015 at 16:47

2 Answers 2

Reset to default
13
$\begingroup$

You can't sort it in linear time.

Suppose you have $n$ items, and you divide them into $\sqrt{n}$ consecutive blocks of $\sqrt{n}$ items each.

You need to take $\sqrt{n} \log \sqrt{n}$ comparisons to sort each one. And there are $\sqrt{n}$ of them, giving $\theta(n \log n)$ time total. And it's easy to see that there can't be more than $n^{3/2}$ inversions in the sequence, since there can't be more than $n$ inversions in each subsequence.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for reply. However, I don't understand your algorithm. Tell more please. And what's is lower bound ? $\endgroup$
    – user40545
    Oct 6, 2015 at 21:38
  • $\begingroup$ @user40545 : $\:$ He didn't give an algorithm. $\;\;\;\;$ $\endgroup$
    – user6973
    Oct 6, 2015 at 22:13
  • $\begingroup$ I am not sure if I understand it correctly. You shown that it impossible to sort faster than $\Omega(n \log n)$. yes ? $\endgroup$
    – user40545
    Oct 7, 2015 at 14:05
  • $\begingroup$ That's right. Even if there are only $n^{3/2}$ inversions, you can't sort using fewer than $\frac{1}{2} n \log n$ comparisons. $\endgroup$
    – Peter Shor
    Oct 7, 2015 at 17:10
  • 5
    $\begingroup$ @user40545 No, it's not. If you had $\Theta$ on both side, or $O$ on both sides, yes -- but what you wrote, with the $O(\cdot)$ and one side and the $\Theta(\cdot)$ on the other is wrong. $\endgroup$
    – Clement C.
    Oct 8, 2015 at 13:57
8
$\begingroup$

This is a topic of "adaptive sorting." As a starter, see the wikipedia page https://en.wikipedia.org/wiki/Adaptive_sort .

It is known that we can sort a sequence of length $n$ with $k$ inversions with $O(n \log (2+k/n))$ comparisons. When $k=O(n^{3/2})$, this translates to $O(n \log n)$. We also have a lower bound of $\Omega(n \log (2+k/n))$. Thus, we know a linear bound is impossible.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I took the liberty to fix the bound. The original implied that sorting can be done with $O(k)$ comparisons, which is easily seen to be impossible for $1\le k\ll n$. $\endgroup$
    – Emil Jeřábek
    Oct 8, 2015 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.