Lower bound for decision tree sorting Theorem. Any decision tree that can sort n elements must have height Q2(nIgn) Proof. The tree must contain > n! leaves, since there are n! possible permutations. a height-h binary tree has≤2 h leaves.Thus,n!≤2 h≥lg(n!) (g is mono. increasing) Ig((nle(Stirling's formula nlgn-nIge 2(n Ig n o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.9© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.9 Lower bound for decision￾tree sorting Theorem. Any decision tree that can sort n elements must have height Ω(n lg n). Proof. The tree must contain ≥ n! leaves, since there are n! possible permutations. A height-h binary tree has ≤ 2h leaves. Thus, n! ≤ 2h . ∴ h ≥ lg(n!) (lg is mono. increasing) ≥ lg ((n/e)n) (Stirling’s formula) = n lg n – n lg e = Ω(n lg n)