Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Evasive Boolean function
open-in-new
<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, an evasive Boolean function f {\displaystyle f} (of n {\displaystyle n} variables) is a <a href="/facts/Boolean_function/uT7E8pqC">Boolean function</a> for which every <a href="/facts/Decision_tree_model/FalJqMSd">decision tree algorithm</a> has running time of exactly n {\displaystyle n} . Consequently, every <a href="/facts/Decision_tree_model/FalJqMSd">decision tree algorithm</a> that represents the function has, at worst case, a running time of n {\displaystyle n} . </p>