\documentclass{slides}
\usepackage{amsmath,amssymb}
\begin{document}
\slide
Bin\"arb\"aume und\\ Komplexit\"at von Sortieralgorithmen
\begin{itemize}
\item[--]
ein Bin\"arbaum mit $k$ Bl\"attern hat\\
$\geq k-1$ innere Knoten, also\\
$\geq 2k-1$ Knoten insgesamt
\item[--]
ein Bin\"arbaum mit $t$ Knoten hat also\\
$\leq \lceil t/2 \rceil$ Bl\"atter
\item[--]
Ein Bin\"arbaum mit Tiefe $h$ hat\\
$\leq 2^{h+1}-1$ Knoten, also\\
$\leq 2^h$ Bl\"atter
\item[--]
ein Bin\"arbaum mit $k$ Bl\"attern hat Tiefe\\
$\geq \rceil \log k \rceil$
\end{itemize}

\slide
\begin{itemize}
\item
Zu jedem deterministischen Sortierverfahren (das auf der Basis von paarweisen \\
Vergleichen operiert) f\"ur Listen der L\"ange $n$ geh\"ort ein\\
 ``bin\"arer Entscheidungsbaum''mit
\begin{itemize}
\item
inneren Knoten f\"ur die\\
 Vergleichsoperationen
\item
Bl\"attern f\"ur die m\"oglichen linearen \\
Ordnungen der $n$ Listenelemente
\end{itemize}
\item
Stirling's Formel (1730)
\[
n! \simeq \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n
\]
\item
Der Entscheidungsbaum hat mindestens $n!$ Bl\"atter, daher eine Tiefe
\[
\geq \lceil \log_2 n! \rceil \in
n \cdot \log n - \theta(n)
\]
\slide

\item
eine \textit{untere Schranke} f\"ur 
die \\
worst-case Komplexit\"at f\"ur des Sortierens ist
also
\[
\theta(n \cdot \log n)
\]
\item
mergesort (mit $n \cdot \log n - n + 1$) und\\
heapsort (mit $2n \cdot \log n$)\\
erreichen diese untere Schranke
\item
auch die mittlere Tiefe (gemittelt \"uber alle Bl\"atter)
von Bin\"arb\"aumen mit $k$ Bl\"attern ist
$\geq \log k$
\item
damit ist
\[
\theta ( n \cdot \log n)
\]
ebenfalls 
eine \textit{untere Schranke} f\"ur die\\ 
\textit{average-case} Komplexit\"at des Sortierens
\item
quicksort erreicht diese Schranke mit\\ 
$2 n \log n - 4 n$
\end{itemize}

\end{document}