\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 3}
\end{center}

\vspace{1cm}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 1, Logarithmus und $\Theta$-Notation (1P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Beweisen oder widerlegen Sie:
\begin{displaymath}
\log_2(n) = \Theta (\log_{10}(n))
\end{displaymath}


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 2, $\Theta$-Notation (2P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Es seien $f(n)$ und $g(n)$ zwei asymptotisch nicht-negative Funktionen, und 
$h(n) := max \{ f(n), g(n) \}$.
Benutzen Sie die Definition der $\Theta$-Notation um zu zeigen, dass
\begin{displaymath}
h(n)  = \Theta (f(n) + g(n))
\end{displaymath}


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 3, $O$-Notation (2P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Beweisen oder widerlegen Sie:
\begin{displaymath}
2^{n+1} = O(2^n)
\end{displaymath}
und
\begin{displaymath}
2^{2n} = O(2^n)
\end{displaymath}



%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 4, Bubblesort (5P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Gegeben sei der folgende Algorithmus:
\vspace{4mm}

\noindent
\textsf{
BUBBLESORT($A$)\\
1 \hspace*{5mm}for $i \leftarrow 1$ to $length[A]$\\
2 \hspace*{10mm} for $j \leftarrow length[A]$ downto $i+1$\\
3 \hspace*{15mm} if $A[j] < A[j-1]$\\
4 \hspace*{20mm} then exchange $A[j] \leftrightarrow A[j-1]$
}
\vspace{4mm}


\noindent
Finden Sie die Invariante f\"ur den for-Loop von Zeile 2 bis 4,
und beweisen Sie die drei wichtigen Eigenschaften der Invariante. (3P)

\noindent
Was ist die worst-case Laufzeit von Bubblesort? (2P)

\end{document}