Recall the lower-bound proof chain (type the Q→A)

Answer

Q: prove a comparison sort needs Omega(n lg n) A: n! <= leaves <= 2^h => h >= lg(n!) = Theta(n lg n)

Correctness forces ≥ n! reachable leaves; a height-h binary tree has ≤ 2^h leaves; so h ≥ lg(n!) = Θ(n lg n). The worst-case comparison count equals the height.