able to output every possible permutation of elements; otherwise, the algorithm would fail for that particular permutation as input. So, its corresponding decision tree must have at least as many leaves as permutations: leaves. Any binary tree with at least leaves has depth at least , so this is a lower bound on the run time of a comparison sorting algorithm. In this case, the existence of numerous comparison-sorting algorithms having this time complexity, such as mergesort and heapsort, demonstrates that the bound is tight. This argument does not use anything about the type of query, so it in fact proves a lower bound for any sorting algorithm that can be modeled as a binary decision tree. In essence, this is a rephrasing of the information-theoretic argument that a correct sorting algorithm must learn at least bits of information about the input sequence. As a result, this also works for randomized decision trees as well. Other decision tree lower bounds do use that the query is a comparison. For example, consider the task of only using comparisons to find the smallest number among numbers. Before the smallest number can be determined, every number except the smallest must "lose" (compare greater) in at least one comparison. So, it takes at least comparisons to find the minimum. (The information-theoretic argument here only gives a lower bound of .) A similar argument works for general lower bounds for computing order statistics. Linear and algebraic decision trees Linear decision trees generalize the above comparison decision trees to computing functions that take real vectors as input. The tests in linear decision trees are linear functions: for a particular choice of real numbers , output the sign of . (Algorithms in this model can only depend on the sign of the output.) Comparison trees are linear decision trees, because the comparison between and corresponds to the linear function . From its definition, linear decision trees can only specify functions whose fibers can be constructed by taking unions and intersections of half-spaces. Algebraic decision trees are a generalization of linear decision trees that allow the test functions to be polynomials of degree . Geometrically, the space is divided into semi-algebraic sets (a generalization of hyperplane). These decision tree models, defined by Rabin and Reingold, are often used for proving lower bounds in computational geometry. For example, Ben-Or showed that element uniqueness (the task of computing , where