This is exercise 2 of the lecture note by Jeff Erickson on decision tree lower bounds.

We say that an array $A[1 \ldots n]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$ (we assume that $n/k$ is an integer), such that the elements in each block are larger than the elements in earlier blocks and smaller than elements in later blocks. The elements within each block need not be sorted.

(a) Describe an algorithm that $k$-sorts an arbitrary array in $O(n \log k)$ time.
(b) Prove that any comparison-based $k$-sorting algorithm requires $\Omega(n \log k)$ comparisons in the worst case.
(c) Describe an algorithm that completely sorts an already $k$-sorted array in $O(n \log(n/k))$ time.
(d) Prove that any comparison-based algorithm to completely sort a $k$-sorted array requires $\Omega(n \log(n/k))$ comparisons in the worst case.

The first problem can be solved by modifying the quicksort algorithm. However, I am stuck with the second problem which asks for a lower bound. My attempt is to use the decision tree technique. I think the number of leaves of the decision tree is at least $((\frac{n}{k})!)^{k}$. Therefore, the height of the decision tree must be $$ H \ge \log ((\frac{n}{k})!)^{k} = k \log (\frac{n}{k})! = \Omega(k \frac{n}{k} \log \frac{n}{k}) = \Omega(n \log \frac{n}{k}),$$ which is not the desired result $\Omega(n \log k)$.

What is wrong with my argument? And how to establish the lower bound $\Omega(n \log k)$?

  • $\begingroup$ Your lower bound is for sorting a $k$-sorted array, whereas the question asks for $k$-sorting an unsorted array. $\endgroup$ – Yuval Filmus Apr 11 '17 at 5:38
  • $\begingroup$ @YuvalFilmus You mean that I have counted the wrong leaves of the decision tree? I am quite confused here. $\endgroup$ – hengxin Apr 11 '17 at 5:39
  • $\begingroup$ Yes, your lower bound is fine, but it's for a different problem... $\endgroup$ – Yuval Filmus Apr 11 '17 at 5:41

From the result of $k$-sorting an array you can tell which elements of the original array were the $n/k$ smallest, the $n/k$ largest, and which belong to each of the other $k-2$ blocks of $n/k$ elements in between. In particular, there are at least $\binom{n}{n/k,\ldots,n/k}$ different leaves, which works out to $\frac{n!}{(n/k)!^k} = \exp \Theta(n\log k)$. This gives you the correct lower bound.

What you calculated is the number of different ways to completely sorted a $k$-sorted permutation. Therefore your lower bound is for sorting a $k$-sorted permutation, and for this task your lower bound is tight: a $k$-sorted permutation can be sorted in $O(n\log (n/k))$.

  • $\begingroup$ $\frac{n!}{(n/k)!^k} = \exp \Theta(n\log k)$, what is the $\exp$? $\endgroup$ – hengxin Apr 11 '17 at 6:25
  • $\begingroup$ The exponential function $e^x$. $\endgroup$ – Yuval Filmus Apr 11 '17 at 6:26

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.