Decision tree model

In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of branching operations based on comparisons of some quantities, the comparisons being assigned unit computational cost. The branching operations are called 'tests' or 'queries'. In this setting the algorithm in question may be viewed as a computation of a Boolean function f : { 0 , 1 } n → { 0 , 1 } {displaystyle f:{0,1}^{n} ightarrow {0,1}} where the input is a series of queries and the output is the final decision. Each query may be dependent on previous queries.