I come across this definition but it's not so clear for me !

An array is partially sorted if the number of inversions is less or equal a constant times the array length. if array length is N then (number of inversions) <= c*N, with c constant.

For me c should be <= 1 is this what they meant ?

For more context : insertion sort running time is linear for partially sorted arrays.

  • 1
    $\begingroup$ Is $c$ fixed or do you get to choose it? I guess the definition wants to be "an array is $c$-partially sorted ... $\leq cN$". $\endgroup$ – Raphael Sep 22 '15 at 14:32

The definition you quote is rather meaningless. More accurately, a sequence of arrays, one of each length $n$, is partially sorted if for some constant $c$, the number of inversions of the array of length $n$ is at most $cn$. (More succinctly, a sequence of arrays is partially sorted if the number of inversions is $O(n)$.) The running time of insertion sort on such a sequence of arrays is $O(n)$, that is, linear.

It doesn't make much sense to say that a single array is partially sorted, since we can always choose $c$ to make the definition hold. If we want to talk about a single array then we need to fix $c$ in advance. Note that $c$ doesn't have to be at most $1$.

  • $\begingroup$ The sequence should be unbounded in array size. $\endgroup$ – Yuval Filmus Sep 22 '15 at 13:02
  • $\begingroup$ To make sure that I get your point let say we have the following sequence of arrays : [10, 20, 5, 25], [100, 200, 50, 250], [1000, 500, 2000, 3000] here n = 4, and c is 1/2 so the number of inversion <= cn = 2; thanks for the detailed answer. $\endgroup$ – morfioce Sep 22 '15 at 13:20
  • $\begingroup$ @morfioce I repeat my comment: the sequence of arrays should be unbounded in length. Otherwise you can "cheat". $\endgroup$ – Yuval Filmus Sep 22 '15 at 13:22
  • $\begingroup$ Can you explain it a bit with an illustrative example ? thanks :) $\endgroup$ – morfioce Sep 22 '15 at 13:46
  • $\begingroup$ @morfioce Any collection of arrays of length 4 is partially sorted (with $c=1.5$). Same goes for any collection of arrays of length at most $n$, with $c=(n-1)/2$. $\endgroup$ – Yuval Filmus Sep 22 '15 at 13:59

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.