Any decision tree that sorts n elements has height ________.

Key idea: any comparison-based decision tree must distinguish all permutations of the input.

• There are n! possible orderings of n distinct elements, so the decision tree must have at least n! distinct leaves (one leaf per permutation).

• If the tree has height h, it can have at most 2^h leaves. Therefore 2^h ≥ n!, which implies h ≥ log2(n!).

• Using Stirling's approximation or the integral bound, log2(n!) = Θ(n log n). For example, log2(n!) = Σ_{i=1}^n log2 i ≥ ∫_1^n log2 x dx = n log2 n − Θ(n) = Θ(n log n).

• Combining these gives h = Ω(n log n).

Conclusion: Any decision tree that sorts n elements must have height Ω(n log n).