Evasive Boolean function

In mathematics, an evasive Boolean function ƒ (of n variables) is a Boolean function for which every decision tree algorithm has running time of exactly n. Consequently, every decision tree algorithm that represents the function has, at worst case, a running time of n.

The following is a Boolean function on the three variables x, y, z:

(where ${\displaystyle \land }$ is the bitwise "and", ${\displaystyle \lor }$ is the bitwise "or", and ${\displaystyle \neg }$ is the bitwise "not").

This function is not evasive, because there is a decision tree that solves it by checking exactly two variables: The algorithm first checks the value of x. If x is true, the algorithm checks the value of y and returns it.

...
Wikipedia