1
$\begingroup$

(Motivated by this question. Also I suspect that my question is a bit too broad)

We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison and each leaf is a permutation. Since there are $n!$ leaves, the minimum tree height is $\Omega(\log (n!)) = \Omega (n \log n)$.

However, it doesn't work for the following problem: find a minimum in the array. For this problem, the results (the leaves) are just indices of the minimum element. There are $n$ of them, and therefore the reasoning above gives $\Omega(\log n)$ lower bound, which is obviously an understatement.

My question: why does this method works for sorting and doesn't work for minimum? Is there some greater intuition or simply "it just happens" and we were "lucky" that sorting has so many possible answers?

I guess the lower bound from decision tree makes perfect sense: we do can ask yes/no questions so that we need $O(\log n)$ answers: namely, we can use binary search for the desired index. My question still remains.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ If you assume that the leaves are one for each index of the minimum, then you don't get a tree, since many different inputs have the same index of the minimum and different sequences of comparisons leading to the same conclusion. $\endgroup$
    – plop
    Aug 7, 2020 at 3:17
  • $\begingroup$ @plop, ah, I see. So what would be the proper structure instead of tree? A DAG, where each vertex is a transitively closed graph with $n$ vertices and edges $u \to v$ if it's known that $u > v$? $\endgroup$
    – user114966
    Aug 7, 2020 at 3:23
  • 1
    $\begingroup$ Actually what I said above is not the right answer. Let me say look at it another way. For each comparison-based algorithm computing minimum you have its decision tree with nodes for each comparison. The thing is that many of the leaves represent the same end result. The same happens, potentially for sorting. For a given algorithm maybe many of the leaves correspond to the same permutations. The thing is that the number of outcomes in sorting is large enough $n!$, that even without repetitions it forces the height of the tree to reach a lower bound $n\log(n)$ ... $\endgroup$
    – plop
    Aug 7, 2020 at 3:30
  • $\begingroup$ ... that then you can show you can attain in some algorithms. The thing with the minimum is that the number of different outcomes is only $n$. But this is only a lower bound, as in sorting, on the number of leaves. But it is a bound that is too conservative. $\endgroup$
    – plop
    Aug 7, 2020 at 3:30
  • 1
    $\begingroup$ There are very interesting approaches for equivalent decision problems. E.g. for the decision problem "is the first entry in the array the minimum" you can picture all the arraaccepted arrays as points in an n-dimensional space. Notice that the solutions form a polyhedron limited by hyperplanes $x_0 < x_i$, $n > i > 0$. Now you can make the argument that in order to check if a point is in the polyhedron you need to check that the point is on the "right" side of every hyperplane. Thus you need $O(n)$ comparisons. $\endgroup$
    – plshelp
    Aug 11, 2020 at 13:32

2 Answers 2

Reset to default
1
$\begingroup$

Interesting question!

The way I understand this is that on sorting it happens that one comparison allows you to discard approximately a half of the possible answers. However on the case of the minimum, one comparison allows you to discard only one possible answer in the worst case. Therefore a proper decision tree for the problem of finding the minimum element has linear height.

It happens in general that the case of sorting is kind of the best we can hope for, as a single comparison can never discard more than half of the answers in the worst case. Think about it this way: if an answer to a comparison were to discard more than half of the possible answers, then the opposite answer to the comparison would discard less than half, and thus one could not expect to discard more than half in the worst case.

That way, we know that for any decision tree with $n$ leaves we can't hope for a height of less than $\log n$ (this is actually true for every kind of tree, because of the same reason), however on certain decisions trees each query is not as helpful and thus the trees get way taller.

I don't know if this actually answers your concern though.

Improve this answer
$\endgroup$
9
  • $\begingroup$ While I agree with what you said, I think it's a bit too specific for minimum problem: i.e. you can't modify it for lower bound on finding both min and max without essentially repeating the proof. I agree with plop's explanation: what matters is the number of possible outcomes. $\endgroup$
    – user114966
    Aug 7, 2020 at 4:05
  • $\begingroup$ But as I described, the number of possible outcomes gives you a weak bound, $\log U$ where $U$ is the number of outcomes. This bound is tight on problems like sorting were effectively you can discard around half outcomes per query. However, on cases like the minimum the bound is very weak as each query rules out few outcomes. So the most important variable seems to be how much do you rule out per query. $\endgroup$
    – Bernardo Subercaseaux
    Aug 7, 2020 at 4:27
  • $\begingroup$ You get a proper bound on the minimum by saying that as each query discards at most 1 element in the worst case, there are paths in the decision tree of length $n-1$, and thus the height of the tree is at least that. For the max-min problem, the issue is that it is not easy to tell how many information you can discard with a query in the worst case. $\endgroup$
    – Bernardo Subercaseaux
    Aug 7, 2020 at 4:29
  • $\begingroup$ @BernardoSubercaseaux When studying complexity of a problem it is strange to think about outcomes being discarded. That's the way one thinks when designing one algorithm. But in this case one is trying to make conclusions about all algorithms that solve the problem. Some inefficient algorithms may not discard any cases after one comparison and go on for very long along a given path, and maybe some are very inefficient along one path, but very efficient along others. $\endgroup$
    – plop
    Aug 7, 2020 at 4:34
  • $\begingroup$ I am aware of that @plop, I refer to the best possible algorithm, that is, the one minimizing the height of its associated tree. So when I say that on the minimum problem you can discard at most 1 outcome per query on the worst case, that statement is to be interpreted as "no possible algorithm can rule out more than 1 outcome per query on the worst case". This can be formalized through the concept of an adversary, which can fool any algorithm that "discards" more outcomes without enough information. $\endgroup$
    – Bernardo Subercaseaux
    Aug 7, 2020 at 4:41
1
$\begingroup$

In the comments I said that $n$ is the number of different possible outcomes of a minimum algorithm and that this is only a lower bound for the number of leaves of the decision trees of the comparison-based minimum algorithms (in which nodes represent the comparisons and edges the results of those comparisons). This is an application of Lemma 1 here, which then implies the bound that you got on the height of the tree. This is Lemma 2 in the linked document. They call this an information theoretic argument.

The reason why it gives such a conservative lower bound for the height of the trees, is that the bound on the number of leaves is too conservative. So, Lemma 1's fault of not being strong enough.

I was curious to see if this method could give a better lower bound if one manages to bound better the number of leaves. For this what we need to do is to have some control on the number of times an outcome of the algorithm is repeated across the leaves.

Suppose a comparison-based algorithm for minimum has decision tree with a maximum of $K$ leaves corresponding to the same outcome.

Then the tree has at most $Kn$ leaves and at most height $\log(n)+\log(K)$. If $n>2(\log(n)+\log(K))$, then none of the paths from root to leaf compares all elements of the array. Since the height of the path is bounded by $\log(n)+\log(K)$, then there are at most that many comparisons in the path. Each comparison looks at $2$ elements, so at most $2(\log(n)+\log(K))$ are inspected. Then we can keep the elements compared in one of the paths fixed and make the other elements smaller than the element that that path chooses as minimum. This input would result on the same output from the algorithm but have a different minimum. So, the algorithm must be incorrect. So, the inequality above must be false. This argument has the flavor of the adversary argument, which applied directly gives the best lower bound for this problem.

Hence $n\leq 2(\log(n)+\log(K))$. From this we get that $\log(K)\geq n/2-\log(n)$, or in other words

$$K\geq 2^{n/2-\log(n)}$$

Now, this tells us that the decision trees for these algorithms will always have at least $K+(n-1)\geq 2^{n/2-\log(n)}+(n-1)$ leaves. So, their height is at least $$\log\left(2^{n/2-\log(n)}+(n-1)\right)\geq n/2-\log(n)$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your final example is very interesting, however I claim that both explanations (mine and yours) are compatible. The bound can be weak because the bound on the leaves is too conservative (your explanation, related to Lemma 1) or because the bound on the height is too conservative (my explanation, related to Lemma 2). In the case of the minimum, one can see that the height is at least n-1 without making any improvement on bounding the number of leaves. $\endgroup$
    – Bernardo Subercaseaux
    Aug 7, 2020 at 16:37
  • $\begingroup$ "decision trees for these algorithms will always have at least $K + (n-1) + \ldots$ leaves" - shouldn't it be $K n$ leaves? $\endgroup$
    – user114966
    Aug 7, 2020 at 19:53
  • 1
    $\begingroup$ @Dmitry $K$ is an upper bound for the number of leaves repeated for each one outcome. For example, maybe the outcome that the $0$-th element is the minimum happens in $K$ leaves and maybe other outcomes have less repetitions. The lower bound that I wrote is counting one outcome meeting the repetition $K$ the other $n-1$ outcomes being counted as one leaf for each. Certainly all outcomes need to have multiple leaves representing them, in this problem, but I am only doing a conservative estimate with the only goal of being less conservative than counting one leaf per outcome. $\endgroup$
    – plop
    Aug 7, 2020 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.