\documentclass[11pt, oneside]{article}

\usepackage{a4, latexsym}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{german}
\usepackage{nopageno}

\date{}

\begin{document}
\noindent
\textsl{Vorlesung Algorithmen, D.~Huson und R.~Rupp, Universit\"at T\"ubingen, WS07/08}

\vspace{1cm}

\begin{center}
\LARGE{Aufgabenblatt 1}
\end{center}

\vspace{1cm}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 1, Sort Geschwindigkeit (1P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Angenommen ein merge sort und ein insertion sort Algorithmus laufen auf dem gleichen Rechner.
F\"ur einen Input der Gr\"osse $n$ braucht der insertion sort $8 \cdot n^2$ Schritte,
der merge sort ben\"otigt f\"ur den gleichen Input $64 \cdot n \cdot \lg n$ Schritte.
F\"ur welche Werte von $n$ ist welcher Algorithmus schneller?




%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 2, Vergleich von Laufzeiten (3P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Bestimmen Sie (f\"ur jede Funktion $f(n)$ und f\"ur jede Zeit $t$ in der Tabelle)
die maximale Gr\"osse $n$ eines Problemes, das in der Zeit $t$ gel\"ost werden kann,
wenn der Algorithmus dazu $f(n)$ Mikrosekunden braucht.

\vspace{2mm}
\begin{tabular}{c | p{14mm} | p{14mm} | p{14mm} | p{14mm} | p{14mm} | p{14mm}  |}
& 1 Sek. & 1 Min. & 1 Std. & 1 Tag & 1 Monat & 1 Jahr \\ %& 100 Jahre\\
\hline
$\lg n$ &&&&&&\\ \hline
$n$ &&&&&&\\ \hline
%$n \cdot \lg n$ &&&&&&&\\ \hline
$n^2$ &&&&&&\\ \hline
%$n^3$ &&&&&&&\\ \hline
$2^n$ &&&&&&\\ \hline
$n!$ &&&&&&\\ \hline
\end{tabular}

\vspace{2mm}



%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 3, Funktionen (6P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%


Wir schreiben $f = O(g)$ f\"ur zwei Funktionen $f$ und $g$, falls
\begin{displaymath}
\exists c,n_0 > 0 \enspace : \enspace \forall n \geq n_0 \enspace : \enspace 0 \leq f(n) \leq c \cdot g(n).
\end{displaymath}
Gegeben sind die folgenden Funktionen:

\vspace{2mm}
\begin{tabular}{l l l}
$f_1(n) = 2^n$
&
$f_4(n) = n!$
&
$f_7(n) = \log_2 \sqrt{\log_2(\log_2 n)}$
\\
$f_2(n) = n^{1 / n}$
&
$f_5(n) = \log_2(\log_2(n^2))$
&
$f_8(n) = n^{\sqrt n}$
\\
$f_3(n) = \sqrt[5]{n}$
&
$f_6(n) = \pi ^{\sqrt 5} n$
&
$f_9(n) = \sum_{i=1} ^n i$
\\
\end{tabular}
\vspace{3mm}

\noindent
Bringen Sie die Funktionen in eine Reihenfolge $f_{i_1} < f_{i_2} < \dots < f_{i_9}$,
so dass gilt: $f_{i_{j}} = O(f_{i_{j+1}})$.

\noindent
Begr\"unden Sie Ihre Antwort, indem Sie f\"ur alle $1 \leq j \leq 8$ zeigen, dass

\begin{displaymath}
\lim_{n \to \infty} \frac{f_{i_j}(n)}{f_{i_{j+1}}(n)} < \infty.
\end{displaymath}

\end{document}