Problem Detail: 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.
Asked By : morfioce
Answered By : Yuval Filmus
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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47442
