1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ (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. $\endgroup$ – FrankW Sep 24 '14 at 7:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 24 '14 at 13:40
  • $\begingroup$ @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). $\endgroup$ – Yuval Filmus Sep 24 '14 at 13:40
  • $\begingroup$ I was assuming that the task is to go from unsorted to $k$-sorted. Now I see, this is indeed unspecified. $\endgroup$ – FrankW Sep 24 '14 at 13:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice proof, But i would like to find N(n,k) , the exact mathematical value of it, using permutaions . $\endgroup$ – Learner Sep 24 '14 at 14:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 24 '14 at 15:13
  • $\begingroup$ thanks for the links. Can you explain how it will be fibonacci numbers when k=1 $\endgroup$ – Learner Sep 24 '14 at 16:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 24 '14 at 16:35
  • $\begingroup$ 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) ? $\endgroup$ – Learner Sep 24 '14 at 16:39

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.