Decision tree model

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, the decision tree model is the <a href="/facts/Model_of_computation/nJr8mHSI">model of computation</a> in which an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> can be considered to be a <a href="/facts/Decision_tree/XDVeGlkJ">decision tree</a>, 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 <a href="/facts/Yes%E2%80%93no_question/v6UgKvHN">yes–no question</a>) and can be performed quickly (say, with unit computational cost), so the worst-case <a href="/facts/Time_complexity/77T62gmf">time complexity</a> 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 <a href="/facts/Lower_bound/YJje9oC2">lower bounds</a> for the complexity of certain classes of computational problems and algorithms. Several variants of decision tree models have been introduced, depending on the <a href="/facts/Computational_model/dq1CR6us">computational model</a> and type of query algorithms are allowed to perform.
For example, a decision tree argument is used to show that a <a href="/facts/Comparison_sort/X1PvE50c">comparison sort</a> of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 items must make 
 
 
 
 n
 log
 ⁡
 (
 n
 )
 
 
 {\displaystyle n\log(n)}
 
 comparisons. For comparison sorts, a query is a comparison of two items 
 
 
 
 a
 ,
 b
 
 
 {\displaystyle a,b}
 
, with two outcomes (assuming no items are equal): either 
 
 
 
 a
 
 b
 
 
 {\displaystyle a>b}
 
. Comparison sorts can be expressed as decision trees in this model, since such sorting algorithms only perform these types of queries.

Decision tree model open-in-new

Decision tree model