Evasive Boolean function

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