Decision tree model

In computational complexity theory, the decision tree model is the model of computation in which an algorithm can be considered to be a decision tree, i.e. a sequence of queries or tests that are done adaptively, so the outcome of previous tests can influence the tests performed next.

Typically, these tests have a small number of outcomes (such as a yes–no question) and can be performed quickly (say, with unit computational cost), so the worst-case time complexity of an algorithm in the decision tree model corresponds to the depth of the corresponding tree. This notion of computational complexity of a problem or an algorithm in the decision tree model is called its decision tree complexity or query complexity.

Decision tree models are instrumental in establishing lower bounds for the complexity of certain classes of computational problems and algorithms. Several variants of decision tree models have been introduced, depending on the computational model and type of query algorithms are allowed to perform.

For example, a decision tree argument is used to show that a comparison sort of ${\displaystyle n}$ items must make ${\displaystyle n\log(n)}$ comparisons. For comparison sorts, a query is a comparison of two items ${\displaystyle a,b}$, with two outcomes (assuming no items are equal): either ${\displaystyle a<b}$ or ${\displaystyle a>b}$. Comparison sorts can be expressed as decision trees in this model, since such sorting algorithms only perform these types of queries.