Untere Schranke für Sortieren durch Vergleichen

Entscheidungsbaum zur Sortierung von 3 Elementen:
gegeben $A,B,C$

Der Entscheidungsbaum zur Sortierung von $n$ Elementen hat $n$! Blätter.

$$\begin{eqnarray*} n!\geq n \cdot (n-1)\cdot (n-2)\cdot \ldots \cdot\frac{n}{2}\geq\left(\left(\frac{n}{2}\right)^{\frac{n}{2}}\right) \end{eqnarray*}$$

$$\begin{eqnarray*} \Rightarrow \log n!&\geq &\log \left(\left(\frac{n}{2}\right)^... ...{2}\\ &\geq&\frac{n}{4}\cdot \log n \mbox{ f\uml {u}r }n \geq 4 \end{eqnarray*}$$

$\Rightarrow$

Ein binärer Baum mit $n!$ Blättern hat mindestens die Höhe $\frac{n}{4}\cdot \log n$.

$\Rightarrow$

Jeder Sortieralgorithmus, der auf Vergleichen beruht, hat als Laufzeit mindestens
$O(n\cdot \log n)$. Dies ist eine untere Schranke.