Complexity of sorting a 1-sorted array

Problem Detail: 

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?

Asked By : blurry

Answered By : D.W.

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54599