Permutations in an k-sorted array

Question

Definition of $k$-sorted array: An array in which an element is at-most $k$ places away from its sorted order.

I have a question in my Algorithms assignment which asks to prove the lower bound to sort a $k$-sorted array as $\Omega(n\log{k})$. I was trying to approach this question by using the standard comparison sort proof ($\Omega(n!)$), where we have $n!$ total permutations of the sequence [$a_1,a_2,\cdots,a_n$]. My friend told me that there are $k^{(n-k)}k!$ permutations of a $k$-sorted array. I'm finding it difficult to prove the same. How should I go about finding the total permutations of a $k$-sorted array?

Try for $n=5,ドル $k=2$.

Total permutation is 3ドル\times 3\times 3\times 2\times 1,ドル First element has 3 possibilities $\{1,2,3\}$; second has 4 possibilities $\{1,2,3,4\},ドル but one position is already taken by the first,so effectively it has $(4-1)$ slots; third has 5 possibilities $\{1,2,3,4,5\},ドル but first and second are there in one of these two, hence 3 possibilities; Fouth one has 4 slots $\{2,3,4,5\}$ and 3 of them are taken? (doubt: because 1st position can also be occupied) , hence 2 , and the last has one.

• FrankW: (1) Every $k$-sorted array is also $k+i$-sorted, for $i>0$. So the problem gets easier with increasing $k$. Your lower bound on the other hand gets larger with increasing $k$. That seems off. (2) The formula from your friend claims that there is only a snigle 1-sorted permutation, which is wrong.
• Yuval Filmus: You never mentioned what kind of lower bound you're interested in. I'm assuming you want to sort a $k$-sorted array, in which case you will need at least $\log_2 N_k$ comparisons, where $N_k$ is the number of $k$-sorted arrays. If so, please make that clear.
• Yuval Filmus: @FrankW The smaller the $k,ドル the stronger the promise on the input array, so the easier the problem is (assuming the problem is indeed to sort the array).
• FrankW: I was assuming that the task is to go from unsorted to $k$-sorted. Now I see, this is indeed unspecified.

Answer 1

Let $N(n,k)$ be the number of $k$-sorted arrays on $n$ elements. At each position we have at most $(2k+1)$ possible elements, giving an upper bound of $(2k+1)^n$. On the other hand, suppose that we divide $\{1,\ldots,n\}$ into $n/k$ blocks of size $k$ (assuming for simplicity that $k$ divides $n$), and apply an arbitrary permutation on each block. All of these arrays are $k$-sorted, showing that $N(n,k) \geq k!^{n/k}$. In total, $$ k!^{n/k} \leq N(n,k) \leq (2k+1)^n \\ \frac{n}{k} (k \log k - k + O(\log k)) \leq \log N(n,k) \leq n \log(2k+1) $$ We conclude that $\log N(n,k) = \Theta(n \log k)$.

For the exact expression, consult a paper of Kløve or the OEIS.

• Learner: Nice proof, But i would like to find N(n,k) , the exact mathematical value of it, using permutaions .
• Yuval Filmus: You might be disappointed, as there is no nice formula for $N(n,k)$. For example, for $k=1$ you get the Fibonacci numbers, and it only gets more complicated, though for every given $k$ you can write a reasonably simple formula. I added a reference giving this formula.
• Learner: thanks for the links. Can you explain how it will be fibonacci numbers when k=1
• Yuval Filmus: Perhaps it's better you worked it out yourself. Try to see how the Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ connects to 1ドル$-sorted permutations. You could even look at some examples, that is, lists of all 1ドル$-sorted permutations for small $n$. The same general idea leads to the formula given in the link.
• Learner: please corect me if i am wrong(Case k=1) : suppose we have a[1,..,n] , Element 1 can take 2 slots namely, 1 and 2 . If the it chooses slot one , then we have F(n-1), id it chooses slot 2 , it means position 2 has to be in slot 1 ,and hence possibilities is F(n-2)..F(n)=F(n-1)+F(n-2) ?