Decision tree model

Summary

The decision tree model measures the cost of a computation by the number of queries it makes to the input, and ignores all other work. An algorithm is a rooted tree. Each inner node asks one question about the input, the answer chooses the branch, and each leaf gives the output. The cost is the depth of the tree, the number of questions in the worst case. The model gives simple lower bounds, such as the bound $\log_2(n!)$ on the number of comparisons needed to sort $n$ items.