|
A worst-case input (for every algorithm) is 1, 1, 1. In every order we choose to check the variables, we have to check all of them. (Note that in general there could be a different worst-case input for every decision tree algorithm.) Hence the functions: "and", "or" (on ''n'' variables) are evasive.
== Binary zero-sum games ==
For the case of binary [[zero-sum game]]s, every [[evaluation function]] is evasive.
In every zero-sum game, the value of the game is achieved by the [[minimax]] algorithm (player 1 tries to maximize the profit, and player 2 tries to minimize the cost).
In the binary case, the max function equals the bitwise "or", and the min function equals the bitwise "and".
A decision tree for this game will be of this form:
* every leaf will have value in {0, 1}.
* every node is connected to one of {"and", "or"}
For every such tree with ''n'' leaves, the running time in the worst case is ''n'' (meaning that the algorithm must check all the leaves):
We will exhibit an [[Adversary (online algorithm)|adversary]] that produces a worst-case input – for every leaf that the algorithm checks, the adversary will answer 0 if the leaf's parent is an Or node, and 1 if the parent is an And node.
This input (0 for all Or nodes' children, and 1 for all And nodes' children) forces the algorithm to check all nodes:
As in the second example
* in order to calculate the ''Or'' result, if all children are 0 we must check them all.
* In order to calculate the ''And'' result, if all children are 1 we must check them all.
==See also==
| 