3
$\begingroup$

When we would like to prove lower bound comparison algorirthm, we often use decision tree, for example sorting by comparisons.
So let's consider find minimum in array $a[1..n]$ by comparison. Lower bound for that problem is commonly known - $n-1$ comparisons.

However, how to use decison tree in order to prove lower bound ?
It seems that it might be (analogously to sorting problem):
$n$ - number of possible results (similiar to $n!$ in sorting).
So the number of comparison (minimal height of tree) is $\log_2(n) < n - 1$.

Believe me, I have tried to understand it, but I can't.

$\endgroup$
  • $\begingroup$ All of this is right. What is it that you don't understand ? $\endgroup$ – Yves Daoust Oct 27 '15 at 11:39
4
$\begingroup$

There is more than one technique to prove a lower bound on the depth of decision trees. One technique you have seen is bounding the depth of a decision tree by the logarithm of the number of its leaves. As you comment, this technique doesn't give the correct lower bound for the case of computing the minimum. However, we can lower bound the depth of a decision tree computing minimum directly.

Take any reachable leaf $\ell$ in a decision tree for minimum, and consider the entire path $p$ leading to it. Construct a graph whose vertices are the input elements $x_1,\ldots,x_n$, two elements $(x_i,x_j)$ being connected if they are compared in $p$. I claim that this graph must be connected, and I show this below. A connected graph on $n$ vertices must have at least $n-1$ edges, and this shows that the leaf must have depth at least $n-1$. In particular, the depth of the decision tree is at least $n-1$.

Now to the proof of the claim. Suppose that the graph contains more than one connected component, say it contains the components $C_1,\ldots,C_m$. Since the leaf $\ell$ is reachable, there is a linear ordering compatible with the results of the comparisons in each connected component $C_i$. We can put together these linear orderings into a linear ordering of all elements in $m!$ different ways. In particular, we can have $C_1 > C_2 > \cdots > C_m$, and we can have $C_1 < C_2 < \cdots < C_m$. This means that it is consistent with the comparisons in $p$ that the minimum is in $C_m$, and it is also consistent that the minimum is in $C_1$. Hence whatever the tree outputs at $\ell$ will be wrong in at least one linear ordering consistent with the comparisons in $p$, showing that the tree doesn't compute the minimum.

$\endgroup$
  • 1
    $\begingroup$ Hmmm, So conclusion: lower bound $\Omega((\log n))$ is correct and right. It say: it is impossible to do it better than $\log (n)$ comparisons. On the other hand you show stronger lower bound - $n-1$. Conclusion: decision tree didn't lie - the tree said true. Analogously we can say, that lower bound for comparison (find minimum) is $1$ comparison. What do you thnik ? Did I get it ? $\endgroup$ – user40545 Oct 27 '15 at 12:58
  • 1
    $\begingroup$ Decision trees are a stronger model of computation than regular algorithms, since they can decide which comparison to make using unlimited computational power. In this case, it so happens that the optimal decision tree can be implemented efficiently, but in other cases (such as 3SUM) this seems not to be the case. So yes, you could say that in this case decision trees reflect the complexity of the problem. In other circumstances they only reflect some of it. $\endgroup$ – Yuval Filmus Oct 27 '15 at 14:27
  • $\begingroup$ "In other circumstances they only reflect some of it." What does it mean ? $\endgroup$ – user40545 Oct 27 '15 at 18:25
  • 1
    $\begingroup$ @user40545 Sometimes the best decision tree has depth $D$ but we don't know of any efficient algorithm that performs $O(D)$ comparison. This is because algorithms have to decide which comparison to make next efficiently, whereas decision trees don't have to (it's specified in advance). That's similar to the difference between Turing machines and circuits. $\endgroup$ – Yuval Filmus Oct 27 '15 at 19:24
  • 1
    $\begingroup$ Not exactly. It depends on your exact computation model. If the Turing machine is only allowed to compare two elements in the input then yes, but this is a rather awkward model to accommodate with a Turing machine. What I wrote was just an analogy. And even going with the analogy, decision trees are like circuits rather than like Turing machines. $\endgroup$ – Yuval Filmus Oct 27 '15 at 21:00
2
$\begingroup$

In this case, the trivial lower bound $\Omega(n)$ holds, because you cannot tell the minimum until you have seen all the values. (By a simple adversary argument, it can take $n/2$ comparisons before the minimum value is processed.)

The information-theoretic bound (decision-tree height) always holds. But it is not always tight.

$\endgroup$

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.