\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 Auswahlproblem}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\begin{verbatim}
SELECT(S, k)
  if |S| < 100 then
    use brute force
  q <- SPLITTER(S)
  S1 <- {s in S | s < q}
  S2 <- {s in S | s > q}
  if |S1| >= k then
    return SELECT(S1, k)
  else if |S1| = k-1 then
    return q
  else 
    return SELECT(S2, k - 1 - |S1|)
\end{verbatim}


Wenn wir die Kosten f\"ur \texttt{SPLITTER} au\ss{}er Acht lassen,
f\"uhrt die Laufzeitanalyse zu der Rekursionsgleichung

\begin{align*}
     T(n) &= O(1) &&\text{f\"ur } n < 100 \text{ und }\\
     T(n) &\leq O(n) + T(3n/4)&& \text{f\"ur } n \geq 100,
\end{align*}
welche sich zu $T(n) = O(n)$ l\"ost.
\end{document}