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 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 decision 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 trees models are instrumental in establishing lower bounds for complexity theory for 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 items must take comparisons. For comparison sorts, a query is a comparison of two items , with two outcomes (assuming no items are equal): either or . Comparison sorts can be expressed as a decision tree in this model, since such sorting algorithms only perform these types of queries. Comparison trees and lower bounds for sorting Decision trees are often employed to understand algorithms for sorting and other similar problems; this was first done by Ford and Johnson. For example, many sorting algorithms are comparison sorts, which means that they only gain information about an input sequence via local comparisons: testing whether , , or . Assuming that the items to be sorted are all distinct and comparable, this can be rephrased as a yes-or-no question: is ? These algorithms can be modeled as binary decision trees, where the queries are comparisons: an internal node corresponds to a query, and the node's children correspond to the next query when the answer to the question is yes or no. For leaf nodes, the output corresponds to a permutation that describes how the input sequence was scrambled from the fully ordered list of items. (The inverse of this permutation, , re-orders the input sequence.) One can show that comparison sorts must use comparisons through a simple argument: for an algorithm to be correct, it must be