New answers tagged

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