\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator {\emst}{emst}
\DeclareMathOperator {\conv}{CH}
\DeclareMathOperator {\argmin}{argmin}
\DeclareMathOperator {\DT}{DT}
\DeclareMathOperator {\UC}{UC}
\DeclareMathOperator {\LC}{LC}

\newtheorem {theorem} {Satz}
\newtheorem {problem}[theorem] {Problem}
\newtheorem {lemma}[theorem] {Lemma}
\newtheorem {observation}[theorem] {Observation}
\newtheorem {corollary}[theorem] {Corollary}
\newtheorem {claim}[theorem] {Claim}


\title{Das Master Theorem}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

Das Master Theorem bietet eine allgemeine Methode, um
eine gro\ss{}e Klasse von Rekursionsgleichungen zu l\"osen.

\begin{theorem}[Master Theorem]
Seien $a \geq 1$ und $b > 1$ Konstanten. Sei $f : \mathbb{N} \rightarrow 
\mathbb{R}^+$ eine Funktion, und sei $T(n)$ durch die folgende Rekursion definiert:
\[
T(n) = aT(n/b) + f(n),
\]
wobei wir $n/b$ wahlweise als $\lfloor n/b \rfloor$ oder
$\lceil n/b \rceil$ interpretieren k\"onnen.
Dann gilt:
\begin{enumerate}
\item Wenn eine Konstante $\eps > 0$ existiert, so dass
$f(n) = O(n^{\log_b a - \eps})$ ist, dann ist
$T(n) = \Theta(n^{\log_b a})$.
\item Wenn $f(n) = \Theta(n^{\log_b a})$ ist, dann
ist
$T(n) = \Theta(n^{\log_b a}\log n)$.
\item Wenn eine Konstante $\eps > 0$ existiert, so dass
$f(n) = \Omega(n^{\log_b a + \eps})$ ist, \emph{und} wenn
eine Konstante $c < 1$ existiert, so dass
$af(n/b) \leq cf(n)$ ist, dann ist
$T(n) = \Theta(f(n))$.
\end{enumerate}
\end{theorem}

Im folgenden betrachten wir einige Beispiele.

\textbf{Karatsuba-Multiplikation.}
Die Karatsuba-Multiplikation hat die Rekursionsgleichung
\[
T(n) = 3 T(n/2) + \alpha n,
\]
f\"ur eine Konstante $\alpha > 0$. Also ist $a=3$, $b=2$, $f(n) = \alpha n$.
Es ist $\log_b a = \log_2 3 \approx 1.58496$, also existiert ein $\eps > 0$ mit 
$f(n) = \alpha n = O(n^{\log_b a - \eps})$ (z.B., $\eps = 0.5$). Daher ist
Fall 1 des Master Theorems anwendbar, und es ist
$T(n) = \Theta(n^{\log_2 3})$.

\textbf{Naive rekursive Multiplikation.}
Bei unserem ersten Versuch zur rekursiven Multiplikation erhielten wir die
Gleichung
\[
T(n) = 4 T(n/2) + \alpha n,
\]
f\"ur eine Konstante $\alpha > 0$. Somit ist $a=4$, $b=2$, $f(n) = \alpha n$.
Es ist $\log_b a = \log_2 4 = 2$, also existiert ein $\eps > 0$ mit 
$f(n) = \alpha n = O(n^{\log_b a - \eps})$ (z.B., $\eps = 0.5$). Wieder ist
Fall 1 des Master Theorems anwendbar, und es ist
$T(n) = \Theta(n^{2})$.

\textbf{Merge Sort.}
Bekanntlich gilt bei Merge Sort
\[
T(n) = 2 T(n/2) + \alpha n,
\]
f\"ur eine Konstante $\alpha > 0$. Also, $a=2$, $b=2$, $f(n) = \alpha n$.
Es ist $\log_b a = \log_2 2 = 1$. Damit ist
$f(n) = \alpha n = \Theta(n^{\log_b a})$. Es gilt also 
Fall 2 des Master Theorems, und 
$T(n) = \Theta(n \log n)$.

\textbf{Bin\"are Suche.}
F\"ur bin\"are Suche haben wir die Rekursion
\[
T(n) = T(n/2) + \alpha,
\]
f\"ur eine Konstante $\alpha > 0$. Also, $a=1$, $b=2$, $f(n) = \alpha$.
Es ist $\log_b a = \log_2 1 = 0$. Damit ist
$f(n) = \alpha = \Theta(n^{\log_b a})$. Nach
Fall 2 des Master Theorems ist
$T(n) = \Theta(\log n)$.

\textbf{Generisches Select.}
In der ersten Vorlesung hatten wir die folgende Rekursion f\"ur den
generischen Select-Algorithmus analysiert:
\[
T(n) = T(3n/4) + \alpha n,
\]
f\"ur eine Konstante $\alpha > 0$. Also, $a=1$, $b=4/3$, $f(n) = \alpha n$.
Es ist $\log_b a = \log_{\frac{4}{3}} 1 = 0$. Damit existiert ein $\eps > 0$,
so dass
$f(n) = \alpha n = \Omega(n^{\log_b a + \eps})$ (z.B. $\eps = 0.4$). Au\ss{}erdem
gilt $af(n/b) = 1 \cdot \alpha \cdot 3n/4 = (3/4) f(n)$. Also existiert ein
$c > 0$ mit $af(n/b) \leq cf(n)$ (z.B. $c = 3/4$).
Somit liefert Fall 3, dass
$T(n) = \Theta(n)$.


\textbf{Deterministisches Select.}
Die Rekursion f\"ur den BFRPT-Algorithmus war
\[
T(n) = T(n/5) + T(3n/4) + \alpha n,
\]
f\"ur eine Konstante $\alpha > 0$. Hier ist das Master Theorem nicht
anwendbar, da die Rekursion nicht dem vorgegebenen Schema folgt. Man
muss sich mit einer anderen Methode behelfen. (Es existiert aber
eine allgemeinere Formulierung des Master Theorems, welche auch diese
Gleichung abdeckt.)

\textbf{Noch eine Ausnahme.}
Betrachte die folgende Gleichung:
\[
T(n) = 4 T(n/4) + n\log^2 n.
\]
Diese Gleichung folgt dem Schema des Master Theorems, und es ist
$a = 4$, $b = 4$ und $f(n) = n \log^2 n$. Also ist $\log_b a = \log_4 4 = 1$.
Trotzdem ist das Master Theorem hier nicht anwendbar, denn es existiert
keine Konstante $\eps > 0$, so dass
$f(n) = n \log^2 n = \Omega(n^{\log_b a + \eps})$ ist.
Es existiert auch keine Konstante $\eps > 0$ mit
$f(n) = n \log^2 n = O(n^{\log_b a - \eps})$, und
es gilt auch nicht $f(n)  = \Theta(n^{\log_b a})$.
Wieder muss man sich mit anderen Methoden behelfen.
\end{document}