A $k$-sorted array is one in which every element is at most distance $k$ from its position when the array is sorted. The complexity of sorting such array is $O(n\log k)$. But if $k=1$, then $\log k=0$ so what happens? What is the complexity of sorting an array where each element is at most one place away from its sorted position?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ If $k=1$ it means that either the minimum is the first element or the second one. Compare the two and eventually swap them. Now you have $n-1$ elements to sort and you can repeat the exact same reasoning. Thus in $n-1$ comparison you have sorted the array, so there's an $O(n)$ algorithm for that. $\endgroup$– BakuriuCommented Mar 17, 2016 at 19:22
-
1$\begingroup$ I will, since it seems to be clearer to everyone else. Why I did not is because in its non-edited version he did not answer what the actual complexity was and your answer helped me understand what I was missing (I was aware of disregarding low coefficients). Thank you. $\endgroup$– blurryCommented Mar 18, 2016 at 15:33
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
When we say an algorithm runs in $O(\lg k)$ time, that is an asymptotic statement. It means that there exists a constant $c$ such that when $k$ is sufficiently large, the running time is $\le c \lg k$. It says nothing about what happens when $k$ is small.
In particular, if we say an algorithm runs in $O(\lg k)$ time, that doesn't necessarily mean that when $k=1$ the running time is 0.
The same kind of comment applies to your question as well. No, it doesn't mean that the running time to sort an array where each element is at most one place away from its sorted position is $O(0)$. Rather, the complexity of that task is $O(n)$.
$\begingroup$
$\endgroup$
3
There is hidden linear time to perform merge part of sorting algorithm.
Linear is less than loglinear, so it was not visible. $\log1=0$, but it means that you will not e.g. heapify, just merge in $O(n)$ (heap structure in case of 1-sorted array degrades to swapping consecutive elements to perform sort).
Inserting element to empty heap (which might be used in such sorting) costs $O(1)$, while putting element to min-heap containing $k$ elements is $O(\log k)$, which is in fact $O(\log k + c)$, so the first looks like it could be substituted with $k=1$ to have cost 0, but the second reveals constant factor in asymptotic notation.
-
1$\begingroup$ I find this answer very hard to understand. What do you mean by "reveal the hidden part and say it is $O(1)$"? The whole algorithm is $O(1)$? That can't be possible because the input could be arbitrarily long. $\endgroup$ Commented Mar 17, 2016 at 19:06
-
1$\begingroup$ The "heapify step" per one element is logk + c, but when k > 1 this is simply logk. When k = 1, we do not use heap so heapify step costs 0, but there is still assingment / read of variable which takes constant time. In notation O(k + 2) we write O(k), but when k = 0, we cannot say this costs nothing, because there are two operations, so I use O(1). $\endgroup$– EvilCommented Mar 17, 2016 at 20:03
-
$\begingroup$ I couldn't even understand this answer until I read D.W.'s. $\endgroup$– stanniusCommented Mar 17, 2016 at 21:32
$\begingroup$
$\endgroup$
There are some studies of tight bounds on sorting, such as Gagie and Nekrich, Tight bounds for online stable sorting , which looks at cost as a function of multiset entropy. These estimates include lower-order terms, so if you look at Table 1 you'll see that both upper bounds include an O(n) term in addition to Hn, so you can't just set H=0 and get zero cost. The O(n) is typically required to verify that all the elements are identical in the H=0 case (n-1 comparisons to be exact).
Unfortunately this makes sorting low-entropy sets disproportionately costly; for instance in radix sort when one radix is single-valued.
I think the entropy is also small for K-sorting; I don't know the exact expression offhand. If all the elements are already ordered that's similar to them being identical; n-1 comparisons are needed.
