= Decision tree model
{wiki}
The <decision tree model> computes a <function> by adaptively querying coordinates of an <input>. Each internal node specifies a query, its outgoing branches represent possible answers, and a leaf supplies the <output>. Later queries may depend on earlier answers. The number of queries on the longest root-to-leaf path is the <decision-tree depth>.<Complexity Measures and Decision Tree Complexity: A Survey by Harry Buhrman and Ronald de Wolf>[classical decision-tree definitions]{ref}
For example, consider the <Boolean function> that returns one if any of its $n$ <input> <bits> is one. Querying in order can stop at the first one, but the all-zero <input> requires all $n$ queries: an unread <bit> might still change the <output>. Thus the worst-case <query complexity> is $n$.
If the <input> <bits> are independent and fair, that same procedure uses only
$$
\mathbb E[Q]=\sum_{j=1}^nP(Q\geq j)=\sum_{j=0}^{n-1}2^{-j}=2(1-2^{-n})
$$
queries on average. Worst-case depth and average cost therefore answer different questions, and an average requires a specified <input> <probability distribution>.
Back to article page
