[Solved]: Why doesn't decision tree work in case find minimum

Problem Detail: 

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.

Asked By : user40545

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48758