3
$\begingroup$

In The Art of Computer Programming 2nd Ed, Vol 3, Section 5.3.1 then discuss a function $S(n)$ which is define as:

$S(n)$ : The minimum number of comparisons that suffice to sort $n$ elements.

Further, the book regards $\lceil \lg n! \rceil$ as the information theoretic lower bound for $S(n)$.

Using merge insertion they also upper bound the number of comparisons by $F(n)$ where

$$F(n) = \sum_{k = 1}^{n} \lceil \lg \tfrac{3}{4} k \rceil$$

So you can get the bound $\lceil \lg n! \rceil \leq S(n) \leq F(n)$, and for any values $n$ where $\lceil \lg n! \rceil = F(n)$ you can find the exact value of $S(n)$.

My questions are:

  1. Why does $S(n)$ not always match the information theoretic lower bound $\lceil \lg n! \rceil$? It seems like if this is all the bits of information we should need, that this is all the comparisons we would need. Why do they differ?

  2. Why is $S(n)$ so difficult to compute? It's discussed in the book some but the reasons are still unclear to me. Do you have to brute force and create every possible decision tree for a given $n$ and determine the longest path? Is there not a more efficient way? It seems that $S(n)$ has only been exactly computed for $n \leq 22$ (See A036604 here).

Improve this question
$\endgroup$
7
  • $\begingroup$ I think that for question 1, what's surprising is that $S(n)$ often reaches or gets very close to $\lceil \lg n!\rceil$. There's no reason to suppose a lower bound "should" be tight, in general. (Similarly, Huffman coding usually doesn't deliver an encoding that actually reaches the LB.) $\endgroup$ – j_random_hacker Apr 9 '19 at 19:35
  • $\begingroup$ Another way to ask this question, the standard way, is what is the time-complexity to find $S(n)$? Is it in P? Is it NP-hard? $\endgroup$ – John L. Apr 9 '19 at 19:40
  • $\begingroup$ @j_random_hacker so the $\lg n!$ bits of information are necessary, but not always sufficient is basically what you're getting at? $\endgroup$ – ryan Apr 9 '19 at 19:41
  • 1
    $\begingroup$ If you're surprised it is hard to compute, you must have some ideas in mind for how to compute it. Can you share what they are? If not, perhaps a good exercise is to try to come up with a way to sort using exactly $\lceil \lg n! \rceil$ comparisons and see if you can figure out whether/why it works; or see if you can come up with a proposed formula for $S(n)$ and see if you can prove whether it works or not. $\endgroup$ – D.W.♦ Apr 9 '19 at 21:26
  • 1
    $\begingroup$ @ryan: That's right. (That's the nature of a lower bound.) It might be that, as with the Huffman example, there are subclasses of instances for which the bound is indeed tight. And it might be that the bound is asymptotically tight, in the sense that the ratio $S(n) / \lceil \lg n! \rceil$ becomes arbitrarily close to 1 as $n$ goes to infinity. $\endgroup$ – j_random_hacker Apr 10 '19 at 6:12
3
$\begingroup$

Let's say the size of the array is such that there are $2^{k-1} < x ≤ 2^k$ possible permutations, so the theoretical lower bound to sort this array is k comparisons.

Any comparison divides the set of possible permutations in two subsets, consistent with each outcome of the comparison. You'd first need a comparison that splits the set of all possible permutations into two subsets, each of size at most $2^{k-1}$. And each subset you need to split into two subsets of size at most $2^{k-2}$ etc. If these subsets don't have the same size, then after j comparisons the size of the largest subset could exceed $2^{k-j}$, and you lost.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The subsets don't necessarily have to be the same size the achieve $k$ comparisons (e.g. $n = 3$ and $x = 6$), but I see your point. So, for the first comparison any arbitrary $A_i < A_j$ should split the permutations in half right? Similarly, for the two subsets, we could compare $A_k < A_{\ell}$ if $k \neq \ell \neq i \neq j$ and this would split the two subsets in half as well I think? The issue of balancing seems to come in when we query an element that has shown up in a previous query on your current path in the decision tree... and I feel strongly that a greedy approach wouldn't work. $\endgroup$ – ryan Apr 9 '19 at 23:53
  • $\begingroup$ @ryan, for the first comparison, sure, and probably for the first few comparisons. But after we've already done a bunch of comparisons (say, after we've done $\Theta(n)$ comparisons), then it seems plausible to me that it might be hard or impossible to find a comparison that splits the set exactly in half -- I don't know, but I don't know how I'd rule it out, either. $\endgroup$ – D.W.♦ Apr 10 '19 at 0:00
  • $\begingroup$ @D.W. It's clearly impossible for large enough $n$, for instance $\lceil \lg 12! \rceil = 29 \neq 30 = S(12)$. Then for $n \geq 12$ we have to do more than $\lg n!$ comparisons, but then when we get back to $n = 20, 21$ we have equivalence again. So it seems to not consistently diverge (maybe it does), when do we need more than the lower bound and when is the lower bound sufficient? $\endgroup$ – ryan Apr 10 '19 at 0:18
  • $\begingroup$ In the section I referenced of TAoCP, they mention that when $n!$ is close to $2^k$ it's unlikely to be solvable in $k$ steps. This intuitively should make sense. For us to get a $k$ step procedure we would need the length every path in the decision tree to be $\leq k$. However, we already know some paths will be relatively short (e.g. when you get lucky and compare all elements in proper order). Thus, some paths being short would force other paths to be longer then resulting in more than $k$ steps worst case. $\endgroup$ – ryan Apr 10 '19 at 0:22

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.