Untere Schranke für (vergleichbasiertes) Sortieren

Gegeben n-Schlüsseln, Queries $a_i \stackrel{?}{<} a_j$. Dies entspricht einen Entscheidungsbaum.

Beobachtung: Jede Permutation $\pi\in S_n$ kommt in mindestens einem Blatt des Entscheidungsbaums vor (|S_n|=n!).$\Rightarrow$ Tiefe des Entscheidungsbaums $\geq \log_2{n!}$.
Stirling: $n! \approx \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$

$$\begin{split} \Rightarrow \text{ Also Tiefe } \geq \log_2 \l... ...}{2}\log{2\pi n} \\ &= n \log_2{n} - \mathcal{O}(n)\end{split}$$