# Tag Info

2

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 ...

0

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 ...

1

In order to bound the number of functions computed by circuits of size $k$, you have at least two options: Construct a large number of circuits of size $k$, which by construction compute different functions. Consider a natural probability distribution on circuits of size $k$, and estimate the probability that two random circuits compute the same function. ...

Top 50 recent answers are included