\documentclass[11pt, a4paper]{article}

\usepackage{ngerman}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage[latin1]{inputenc}
\usepackage[pdftex,             
            pdfpagelabels,
            colorlinks=true,           % Links nicht farbig umrahmen, sondern als farbigen Text
            urlcolor=colorBlue,        % Farbe für externe Verweise, \href{...}{...}
            filecolor=colorGreen,      % Farbe für lokale Verweise, \href{...}{...}
            linkcolor=colorRed,        % Farbe für interne Verweise, \ref{...} und \pageref{...}
            pdftitle={},
            pdfauthor={Jan Hendrik Dithmar},
            pdfsubject={},
            pdfkeywords={},
            pdfpagemode=None,          % Navigationsleiste beim Start ausblenden 
            % pdfpagemode=UseThumbs,     % Thumbnails beim Start anzeigen
            % pdfpagemode=UseOutlines,   % Lesezeichen beim Start anzeigen
            % pdfpagemode=FullScreen,    % im Vollbildmodus starten
            % pdfstartpage=2,            % spezielle Startseite festlegen
            bookmarks,
            % bookmarksopen,             % alle Lesezeichen aufklappen
            % bookmarksopenlevel=2,      % Tiefe, bis zu welcher die Lesezeichen aufgeklappt werden sollen
            bookmarksnumbered,         % Lesezeichen nummerieren
            pdfstartview=FitH,         % Seite auf voller Breite anzeigen
            pagebackref
           ]{hyperref}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}

\thispagestyle{empty}

\title{Programmierung II - Übungsblatt 6 \\
	Übungsgruppe Do 14-16 \\	
	Andreas Augustin}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
	Dirk Heine (Matrikelnummer 2030941) \\
	Andreas Glitsch (Matrikelnummer 2026130)}
\date{}

\maketitle

\newpage

\section*{Aufgabe 1}

\subsubsection*{(a)}
{\bfseries Zu zeigen:} $f(n) \in \OnotO(g(n)) \Leftrightarrow g(n) \in \Omega(f(n))$.\\
{\bfseries Beweis:}
\begin{eqnarray*}
	f(n) \in \OnotO(g(n)) & \stackrel{Def.}{\Longleftrightarrow} & \exists c, n_0 \in \SetN, c>0, n \ge 0: \forall n \ge n_0: 0 \le f(n) \le cg(n) \\
	& \stackrel{c>0}{\Longleftrightarrow} & \exists c,n_0 \in \SetN, c>0, n \ge 0: \forall n \ge n_0: 0 \le \frac{1}{c}f(n) \le g(n) \\
	& \stackrel{c' := \frac{1}{c}}{\Longleftrightarrow} & \exists c,n_0 \in \SetN, c>0, n \ge 0: \forall n \ge n_0: 0 \le c'f(n) \le g(n) \\
	& \stackrel{Def.}{\Longleftrightarrow} & g(n) \in \Omega(f(n))
\end{eqnarray*} \QED

\subsubsection*{(b)}
{\bfseries Zu zeigen:} $f(\frac{n}{2}) \in \Theta(f(n))$ \\
{\bfseries Beweis:} \\
(Gegen-)Beispiel: $f(n) = exp(n)$. Das bedeutet:
$$e^{\frac{n}{2}} \in \Theta(e^n) \Leftrightarrow e^{\frac{n}{2}} \in \OnotO(e^n) \AND e^{\frac{n}{2}} \in \Omega(e^n)$$
\begin{eqnarray*}
	e^{\frac{n}{2}} \in \OnotO(e^n) & \Leftrightarrow & \exists c>0; n_0 \in \SetN: \forall n \ge n_0: e^{\frac{n}{2}} \le c e^n \\
	& \Leftrightarrow & \exists c>0; n_0 \in \SetN: \forall n \ge n_0: \frac{1}{e^{\frac{n}{2}}} \le c
\end{eqnarray*}
Dies ist für $c=1$ offensichtlich erfüllt.
\begin{eqnarray*}
	e^{\frac{n}{2}} \in \Omega(e^n) & \Leftrightarrow & \exists c>0; n_0 \in \SetN: \forall n \ge n_0: e^{\frac{n}{2}} \ge c \cdot e^n \\
	& \Leftrightarrow & \exists c>0; n_0 \in \SetN: \forall n \ge n_0: \frac{1}{e^{\frac{n}{2}}} \ge c
\end{eqnarray*}
Dies wäre für $c=0$ erfüllt. Da jedoch $c>0$ sein muss, gibt es kein $c$ für das $\frac{1}{e^{\frac{n}{2}}} \ge c$ gilt. \FLASH \\
Somit gilt die Behauptung $f(\frac{n}{2}) \in \Theta(f(n))$ nicht. \QED

\subsubsection*{(c)}
{\bfseries Zu zeigen:} $f(n) \cdot g(n) \in \Theta(max(f(n),g(n)))$ \\
{\bfseries Beweis:} \\
Beispielsweise wählt man $f(n) := n$ und $g(n) := n^2$. Dann gilt $\forall n > 1$ immer $g(n) > f(n)$ und auch $g(n) = max(f(n),g(n))$. Würde die Behauptung gelten, dann
wäre $n \cdot n^2 = n^3 \in \Theta(n^2)$. Da $\lim_{n \to \infty} \frac{n^2}{n \cdot n^2} = 0$ gilt, so gilt auch $n \in o(n^3) \subset \OnotO(n^3)$.
Damit aber $n^3 \in \Theta(n^2)$ gelten kann, müsste auch $n^3 \in \OnotO(n^2)$ gelten. \\
Dies ist unmöglich, da gelten müsste: $$\exists c > 0, n_0 \in \SetN: \forall n \ge n_0: 0 \le n^3 < cn$$
Da $n>0$ gilt damit auch $0 \le n^2 < c \quad \forall n \ge n_0 \quad \FLASH$ \\
Diese Aussage ist nicht erfüllbar.

\subsubsection*{(d)}
{\bfseries Zu zeigen:} $o(f(n)) \cap \omega(f(n)) = \emptyset$ \\
{\bfseries Beweis:} \\
$\text{Sei } o(f(n)) \cap \omega(f(n)) \ne \emptyset$
\begin{eqnarray*}
	& \Rightarrow & \exists g(n) \in o(f(n)) \cap \omega(f(n)) \\
	& \Rightarrow & \exists g(n): g(n) \in o(f(n)) \AND g(n) \in \omega(f(n)) \\
	& \Rightarrow & \exists g(n): \forall c>0 \; \exists 0 < n_1 \in \SetN: \forall n \ge n_1: 0 \le f(n) < cg(n) \\
	& & \AND \forall c>0 \; \exists 0 < n_2 \in \SetN: \forall n \ge n_2: 0 \le cg(n) < f(n) \\
	& \stackrel{(*)}{\Rightarrow} & \exists g(n): \forall c>0 \; \exists 0 < n' \in \SetN: \forall n \ge n': 0 \le f(n) < cg(n) \\
	& & \AND 0 \le cg(n) < f(n) \\
	& \Rightarrow & \exists g(n): \forall c>0 \; \exists 0<n' \in \SetN: \forall n \ge n': 0 \le cg(n) < f(n) < cg(n) \quad \FLASH
\end{eqnarray*}
$(*): \quad n' := max \{n_1, n_2\}$ \\
Damit ist gezeigt, dass $o(f(n)) \cap \omega(f(n)) = \emptyset$. \QED

\subsubsection*{(f)}
{\bfseries Zu zeigen:} Für $g(n) \in o(f(n)): f(n)+g(n) \in \Theta(f(n))$. \\
{\bfseries Beweis:}
$$f(n)+g(n) \in \Theta(f(n)) \Leftrightarrow \exists c_1,c_2 >0, n_0 >0: \forall n \ge n_0: 0 \le c_1f(n) \le f(n)+g(n) \le c_2f(n)$$
Wir wissen, dass $g(n) \in o(f(n))$ ist und \\
$\forall c>0, \exists \; n_0 > 0: \forall n \ge n_0: 0 \le g(n) < cf(n)$. \\
Dann gilt
$$\forall n\ge n_0: 0 \le f(n) \le f(n)+g(n) \le f(n)+f(n)$$
und wir können folgern:
$$\forall n \ge n_0: 0 \le c_1 f(n) \le f(n)+g(n) \le 2 f(n) \le c_2f(n)$$
Die Aussage ist für $c_1=1$ und $c_2=2$ offensichtlich erfüllt und somit bewiesen. \QED

\section*{Aufgabe 2}
\begin{enumerate}[(a)]
	\item Reflexivität: $\forall f: f \in \Theta(f)$ \\
		Um $f \in \Theta(f)$ zu zeigen, zeigt man $f \in \OnotO(f)$ und $f \in \Omega(f)$
		\begin{itemize}
			\item $f \in \OnotO(f) \Leftrightarrow \exists c>0: f \le c \cdot f$ \\
				Dies ist offensichtlich erfüllt $\forall c>0$ und $\forall f \ge 0$
			\item $f \in \Omega(f) \Leftrightarrow \exists c>0: f \ge c \cdot f$ \\
				Diese Aussage ist erfüllt $\forall c>0$ und $\forall f \le 0$.
		\end{itemize}
		Somit gilt $f \in \Theta(f)$.
	\item Symmetrie: $\forall f,g: f \in \Theta(g) \Rightarrow g \in \Theta(f)$ \\
		Man nimmt auch hier wieder zur Hilfe $f \in \Theta(g) \Leftrightarrow f \in \OnotO(g) \AND f \in \Omega(g)$
		$$f \in \OnotO(g) \Leftrightarrow \exists c>0: f \le c \cdot g$$
		$$f \in \Omega(g) \Leftrightarrow \exists c>0: f \ge c \cdot g$$
		\begin{eqnarray*}
			f \le c \cdot g & \AND & f \ge c \cdot g \\
			\frac{1}{c} \cdot f \le g & \AND & \frac{1}{c} \cdot f \ge g \\
			\stackrel{c' := \frac{1}{c}}{\Rightarrow} c' \cdot f \le g & \AND & c' \cdot f \ge g \\
			g \in \Omega(f) & \AND & g \in \OnotO(f)
		\end{eqnarray*}
		$$\Rightarrow g \in \Theta(f)$$
	\item Transitivität: $\forall f,g,h: f \in \Theta(g) \AND g \in \Theta(h) \Rightarrow f \in \Theta(h)$
		Zeige dazu:
		\begin{itemize}
			\item $f \in \OnotO(g) \AND g \in \OnotO(h) \Rightarrow f \in \OnotO(h)$
				\begin{eqnarray*}
					f \in \OnotO(g) & \Leftrightarrow & \exists c_f > 0: f \le c_f \cdot g \\
					g \in \OnotO(h) & \Leftrightarrow & \exists c_g > 0: g \le c_g \cdot h
				\end{eqnarray*}
				Sei $c=c_f \cdot c_g$ und $n_0 = \max\{n_f, n_g\}$ dann gilt für alle $n \ge n_0$:
				$$f \le c_f \cdot g \le c_f c_g \cdot h \le c \cdot h$$
				$\Rightarrow \exists c>0; n_0 > 0$ sodass $\forall n \ge n_0$ gilt:
				$$f \le c \cdot h \Leftrightarrow f \in \OnotO(h)$$
			\item $f \in \Omega(g) \AND g \in \Omega(h) \Rightarrow f \in \Omega(h)$
				\begin{eqnarray*}
					f \in \Omega(g) & \Leftrightarrow & \exists c_f' > 0: f \ge c_f' \cdot g \\
					g \in \Omega(h) & \Leftrightarrow & \exists c_g' > 0: g \ge c_g' \cdot h
				\end{eqnarray*}
				Sei $c'=c_f' \cdot c_g'$ und $n_0' = \max\{n_f', n_g'\}$ dann gilt für alle $n \ge n_0'$:
				$$f \ge c_f' \cdot g \ge c_f' c_g' \cdot h \ge c' \cdot h$$
				$\Rightarrow \exists c'>0$ sodass gilt:
				$$f \ge c' \cdot h \Leftrightarrow f \in \Omega(h)$$
		\end{itemize}
\end{enumerate} \QED

\section*{Aufgabe 3}
Anordnung:
$$ln(n); \; \sqrt[3]{n}; \; e^{\sqrt{n}}; \; n!; \; n^n$$
Begründung: \\
$(*)$: l'Hôpital
\subsubsection*{(i)}
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{|ln(n)|}{|\sqrt[3]{n}|} & = & \lim_{n \to \infty} \frac{|ln(n)|}{|n^{\frac{1}{3}}|} \\
	& \stackrel{(*)}{=} & \lim_{n \to \infty} \frac{\left|\frac{1}{n}\right|}{\left|\frac{1}{3n^{\frac{2}{3}}}\right|} \\
	& = & \lim_{n \to \infty} \frac{|3|}{|\sqrt[3]{n}|} = 0
\end{eqnarray*}

\subsubsection*{(ii)}
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{|\sqrt[3]{n}|}{|e^{\sqrt{n}}|} & \stackrel{(*)}{=} & \lim_{n \to \infty} \frac{\left|\frac{1}{3n^{\frac{2}{3}}}\right|}{\left|\frac{e^{\sqrt{n}}}{2 \sqrt{n}}\right|} \\
	& = & \lim_{n \to \infty} \frac{|2 n^{\frac{1}{2}}|}{|e^{\sqrt{n}} \cdot 3 \cdot n^{\frac{2}{3}}|} \\
	& = & \lim_{n \to \infty} \frac{|2|}{|3n^{\frac{1}{6}} \cdot e^{\sqrt{n}}|} \\
	& = & 0
\end{eqnarray*}

\subsubsection*{(iii)}
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{|e^{\sqrt{n}}|}{|n!|} & = & \lim_{n \to \infty} \frac{\left|\prod_{i=0}^{\sqrt{n}-1} e\right|}{\left|\prod_{i=0}^{n-1} (n-i)\right|} \\
	& = & \lim_{n \to \infty} \frac{\left|\prod_{i=0}^{\sqrt{n}-1} e\right|}{\left|\prod_{i=0}^{\sqrt{n}-1} (n-i) \cdot \prod_{i=\sqrt{n}}^{n-1} (n-i)\right|} \\
	& = & \lim_{n \to \infty} \frac{\left|\prod_{i=0}^{\sqrt{n}-1} e\right| \cdot |1|}{\left|\prod_{i=0}^{\sqrt{n}-1} (n-i)\right| \cdot \left|\prod_{i=\sqrt{n}}^{n-1} (n-i)\right|} \\
	& = & \lim_{n \to \infty} \left(\frac{\left|\prod_{i=0}^{\sqrt{n}-1} e\right|}{\left|\prod_{i=0}^{\sqrt{n}-1} (n-i)\right|} \cdot \frac{|1|}{\left|\prod_{i=\sqrt{n}}^{n-1} (n-i)\right|}\right) \\
	& = & \lim_{n \to \infty} \left(\prod_{i=0}^{\sqrt{n}-1} \frac{e}{n-i} \cdot \prod_{i=\sqrt{n}}^{n-1} \frac{1}{n-i}\right) \\
	& = & 0
\end{eqnarray*}

\subsubsection*{(iv)}
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{|n!|}{|n^n|} & = & \lim_{n \to \infty} \frac{|1 \cdot 2 \cdot ... \cdot n|}{|n \cdot n \cdot ... \cdot n|} \\
	& = & \lim_{n \to \infty} \frac{|1|}{|n \cdot \frac{n}{2} \cdot ... \cdot 1|} \\
	& = & 0
\end{eqnarray*}


\section*{Aufgabe 4}

\subsubsection*{(a)}
{\bfseries Zu zeigen:} $2+2log(n) \in \OnotO(log(n))$ \\
{\bfseries Beweis:}
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{|2(log(n)+1)|}{|log(n)|} & = & \lim_{n \to \infty} 2 \cdot \frac{|log(n)+1|}{|log(n)|} \\
	& = & 2 \cdot \lim_{n \to \infty} \left(\underbrace{\frac{|log(n)|}{|log(n)|} + \frac{1}{|log(n)|}}_{\underset{n \to \infty}{\to} 1}\right) \\
	& = & 2 \cdot 1 \\
	& = & 2
\end{eqnarray*}
$$\Rightarrow 2+2log(n) \in \OnotO(log(n))$$ \QED

\subsubsection*{(c)}
{\bfseries Zu zeigen:} $3^n \in \OnotO(2^n)$ \\
{\bfseries Beweis:}
$$\lim_{n \to \infty} \frac{3^n}{2^n} = \infty$$
Es gilt
$$\lim_{n \to \infty} \frac{2^n}{3^n} = 0$$
und damit auch $2^n \in o(3^n)$. Somit kann $3^n \in \OnotO(2^n)$ nach der Definition von $\OnotO$ nicht gelten. \FLASH

\subsubsection*{(d)}
{\bfseries Zu zeigen:} $2^n \in \Theta(3^n)$ \\
{\bfseries Beweis:} \\
Um die Behauptung zu zeigen wird gezeigt:
$$2^n \in \OnotO(3^n) \AND 2^n \in \Omega(3^n)$$
\begin{itemize}
	\item $2^n \in \OnotO(3^n)$ \\
		Bilde hierzu:
		$$\lim_{n \to \infty} \frac{2^n}{3^n} = 0 \Rightarrow 2^n \in \OnotO(3^n)$$
	\item $2^n \in \Omega(3^n) \Leftrightarrow \exists c>0; n_0 \in \SetN: \forall n \ge n_0: 2^n \ge c \cdot 3^n$ \\
		Damit dies gilt, muss $c<0$ sein, was nach Voraussetzung nicht gilt. \FLASH
\end{itemize}

\end{document}
