Decision tree model

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 a unit computational cost. Several variants of decision tree models may be considered, depending on the complexity of the operations allowed in the computation of a single comparison and the way of branching.

Decision trees models are instrumental in establishing lower bounds for computational complexity for certain classes of computational problems and algorithms: the lower bound for worst-case computational complexity is proportional to the largest depth among the decision trees for all possible inputs for a given computational problem.

Simple decision tree

The model in which every decision is based on the comparison of two numbers within constant time is called simply a decision tree model. It was introduced to establish computational complexity of sorting and searching.

The simplest illustration of this lower bound technique is for the problem of finding the smallest number among n numbers using only comparisons. It this case the decision tree model is a binary tree. Algorithms for this searching problem may result in n different outcomes (since any of the n given numbers may turn out to be the smallest). It is known that the depth of a binary tree with n leaves is at most $\log n$, which gives the lowed bound of $\Omega (\log n)$ for the searching problem.

Along the same lines the lower bound of $\Omega (n\log n)$ for sorting may be proved.