\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 11}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
				Dirk Heine - Matrikelnummer 2030941 \\
		Di, 9-11 Uhr, Andreas Augustin \\
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage
\section*{Aufgabe 1}
{\bfseries bearbeitet von Dirk Heine}
\subsubsection*{(a)}
$$f(x)= 
\begin{cases}
1 \text{ falls $x$ gerade} \\
0 \text{ sonst}
\end{cases}
$$
$$g(x)= 
\begin{cases}
0 \text{ falls $x$ gerade} \\
1 \text{ sonst}
\end{cases}
$$
\\[0.3cm]
Beweis: \\
\noindent Angenommen $\exists c \in \SetR$ so dass $g(n) \leq c \cdot f(n)\ \ \forall n \geq n_0$. \\
Dann müsste gelten $g(2n_0+1) \leq c \cdot f(2n_0+1) \Leftrightarrow 1 \leq 0.$
\FLASH \\
$\Rightarrow g \notin \OnotO(f)$. \\[0.3cm]
\noindent Angenommen $\exists c \in \SetR$ so dass $f(n) \leq c \cdot g(n)\ \ \forall n \geq n_0$. \\
Dann müsste gelten $f(2n_0) \leq c \cdot g(2n_0) \Leftrightarrow 1 \leq 0.$
\FLASH \\
$\Rightarrow f \notin \OnotO(g)$.

\newpage

\section*{Aufgabe 2}
{\bfseries bearbeitet von Jan Hendrik Dithmar} \\[0.3cm]
Folgende Funktionen sind nach ihrem asymptotischen Wachstum für $n \to \infty$ wie folgt geordnet, beginnend mit der Funktion mit dem schwächsten Wachstum bis zur Funktion mit dem stärksten Wachstum:
$$\log(n), \quad \sqrt{n}, \quad n \cdot \log(n), \quad n^{\frac{4}{3}}, \quad n^2 \cdot \log(n), \quad n^{2+\varepsilon} (\varepsilon > 0), \quad e^{\sqrt{n}}, \quad 2^n$$
Vorbemerkungen:
\begin{enumerate}
	\item Unter $\log(n)$ soll der natürliche Logarithmus $\ln(n)$ verstanden werden.
	\item Aus der Analysis wird als bekannt vorausgesetzt:
		$$\lim_{n \to \infty} \frac{\log(n)}{n^{\alpha}} = 0 \text{ für jedes } \alpha > 0$$
	\item Aus der Analysis wird die 2. Regel von de l'Hospital als bekannt vorausgesetzt.
\end{enumerate}

\begin{itemize}
	\item $$\displaystyle \lim_{n \to \infty} \frac{\log(n)}{\sqrt{n}} = \lim_{n \to \infty} \frac{\log(n)}{n^{\frac{1}{2}}} = 0 \quad \text{wegen 2.}$$
	\item $$\displaystyle \lim_{n \to \infty} \frac{\sqrt{n}}{n \cdot \log(n)} = \lim_{n \to \infty} \frac{1}{\sqrt{n} \cdot \log(n)} = 0$$
	\item $$\displaystyle \lim_{n \to \infty} \frac{n \cdot \log(n)}{n^{\frac{4}{3}}} = \lim_{n \to \infty} \frac{\log(n)}{n^{\frac{1}{3}}} = 0 \quad \text{wegen 2.}$$
	\item $$\displaystyle \lim_{n \to \infty} \frac{n^{\frac{4}{3}}}{n^2 \cdot \log(n)} = \lim_{n \to \infty} \frac{1}{n^{\frac{2}{3}} \cdot \log(n)} = 0$$
	\item $$\displaystyle \lim_{n \to \infty} \frac{n^2 \cdot \log(n)}{n^{2+\varepsilon}} = \lim_{n \to \infty} \frac{\log(n)}{n^{\varepsilon}} = 0 \quad \text{wegen 2. mit } \alpha=\varepsilon>0$$
	\item
		\begin{eqnarray*}
			\lim_{n \to \infty} \frac{n^{2+\varepsilon}}{3^{\sqrt{n}}} & = & \lim_{n \to \infty} \frac{n^{2+\varepsilon}}{e^{\sqrt{n} \cdot \ln(3)}} \quad \varepsilon > 0 \\
			& \stackrel{3.}{=} & \lim_{n \to \infty} \frac{(2+\varepsilon) \cdot n^{1+\varepsilon}}{e^{\sqrt{n} \cdot \ln(3)} \cdot (\ln(3)) \cdot \frac{1}{2\sqrt{n}}} \\
			& = & \frac{\prod_{i=4}^4 (i+2\varepsilon)}{\ln(3)} \cdot \lim_{n \to \infty} \frac{n^{\frac{3}{2}+\varepsilon}}{e^{\sqrt{n} \cdot \ln(3)}} \\
			& \stackrel{3.}{=} & \frac{2 \cdot (2+\varepsilon)}{\ln(3)} \cdot \lim_{n \to \infty} \frac{(\frac{3}{2}+\varepsilon) \cdot n^{\frac{1}{2}+\varepsilon}}{e^{\sqrt{n} \cdot \ln(3)} \cdot \ln(3) \cdot \frac{1}{2\sqrt{n}}} \\
			& = & \frac{\prod_{i=3}^4 (i+2\varepsilon)}{(\ln(3))^2} \cdot \lim_{n \to \infty} \frac{n^{1+\varepsilon}}{e^{\sqrt{n} \cdot \ln(3)}} \\
			& \stackrel{3.}{=} & \frac{2^2 \cdot (2+\varepsilon) \cdot (\frac{3}{2}+\varepsilon)}{(\ln(3))^2} \cdot \lim_{n \to \infty} \frac{(1+\varepsilon) \cdot n^{\varepsilon}}{e^{\sqrt{n} \cdot \ln(3)} \cdot \ln(3) \cdot \frac{1}{2\sqrt{n}}} \\
			& = & \frac{\prod_{i=2}^4 (i+2\varepsilon)}{(\ln(3))^3} \cdot \lim_{n \to \infty} \frac{n^{\varepsilon+\frac{1}{2}}}{e^{\sqrt{n} \cdot \ln(3)}} \\
			& \stackrel{3.}{=} & \frac{2^3 \cdot (2+\varepsilon) \cdot (\frac{3}{2}+\varepsilon) \cdot (1+\varepsilon)}{(\ln(3))^3} \cdot \lim_{n \to \infty} \frac{(\frac{1}{2}+\varepsilon) \cdot n^{\varepsilon-\frac{1}{2}}}{e^{\sqrt{n} \cdot \ln(3)} \cdot \ln(3) \cdot \frac{1}{2\sqrt{n}}} \\
			& = & \frac{\prod_{i=1}^4 (i+2\varepsilon)}{(\ln(3))^4} \cdot \lim_{n \to \infty} \frac{n^\varepsilon}{e^{\sqrt{n} \cdot \ln(3)}} \\
			& \stackrel{3.}{=} & \frac{2^4 \cdot (2+\varepsilon) \cdot (\frac{3}{2}+\varepsilon) \cdot (1+\varepsilon) \cdot (\frac{1}{2}+\varepsilon)}{(\ln(3))^4} \cdot \lim_{n \to \infty} \frac{\varepsilon \cdot n^{\varepsilon-1}}{e^{\sqrt{n} \cdot \ln(3)} \cdot \ln(3) \cdot \frac{1}{2\sqrt{n}}} \\
			& = & \underbrace{\frac{\prod_{i=0}^4 (i+2\varepsilon)}{(\ln(3))^5}}_{=: k_\varepsilon > 0} \cdot \lim_{n \to \infty} \frac{n^{\varepsilon-\frac{1}{2}}}{e^{\sqrt{n} \cdot \ln(3)}} \\
			& = & k_\varepsilon \cdot \lim_{n \to \infty} \frac{n^{\varepsilon-\frac{1}{2}}}{e^{\sqrt{n} \cdot \ln(3)}} \\
			& = & k_\varepsilon \cdot \lim_{n \to \infty} \frac{1}{n^{\frac{1}{2}-\varepsilon} \cdot 3^{\sqrt{n}}} = 0 \quad \text{falls gilt: } 0 < \varepsilon \le \frac{1}{2}
		\end{eqnarray*}
		Andernfalls setze man das Verfahren fort, bis der Exponent von $n$, nämlich $2+\varepsilon - m \cdot \frac{1}{2}$ für ein $m \in \SetZ^+$ erstmals negativ ist.
		$$\Longrightarrow \lim_{n \to \infty} \frac{n^{2+\varepsilon}}{3^{\sqrt{n}}} = 0 \quad (\varepsilon > 0)$$
	\item Es gilt:
		$$3^{\sqrt{n}} < (2^2)^{\sqrt{n}} = 2^{2 \cdot \sqrt{n}} \stackrel{n \ge 4}{\le} 2^{\sqrt{n} \cdot \sqrt{n}} = 2^n$$
		$$\Longrightarrow 3^{\sqrt{n}} < 2^n \quad \forall n \ge 4$$
		$$\Longleftrightarrow \frac{3^{\sqrt{n}}}{2^n} < 1 \quad \forall n \ge 4 \quad (I)$$
		\begin{eqnarray*}
			\lim_{n \to \infty} \frac{3^{\sqrt{n}}}{2^n} & = & \lim_{n \to \infty} \frac{e^{\sqrt{n} \cdot \ln(3)}}{e^{n \cdot \ln(2)}} \\
			& \stackrel{3.}{=} & \lim_{n \to \infty} \frac{e^{\sqrt{n} \cdot \ln(3)} \cdot \ln(3) \cdot \frac{1}{2\sqrt{n}}}{e^{n \cdot \ln(2)} \cdot \ln(2)} \\
			& = & \frac{\ln(3)}{2 \cdot \ln(2)} \cdot \lim_{n \to \infty} \left(\underbrace{\frac{3^{\sqrt{n}}}{2^n}}_{<1, \forall n \ge 4} \cdot \frac{1}{\sqrt{n}}\right) \\
			& \stackrel{(I)}{\le} & \frac{\ln(3)}{2 \cdot \ln(2)} \cdot \lim_{n \to \infty} \left(1 \cdot \frac{1}{\sqrt{n}}\right) = 0
		\end{eqnarray*}
\end{itemize}

\newpage

\section*{Aufgabe 3}
{\bfseries bearbeitet von Jan Hendrik Dithmar} \\[0.3cm]
\begin{itemize}
\item $g \in \Theta(f) \Longrightarrow f \in \Theta(g)$: \\
Zeige dazu:
\begin{eqnarray*}
	g \in \OnotO(f) & \Longleftrightarrow & \exists c > 0: g \le_{\text{fü}} c \cdot f \\
	& \Longleftrightarrow & \frac{1}{c} \cdot g \le_{\text{fü}} f \\
	& \Longleftrightarrow & c' \cdot g \le_{\text{fü}} f \quad \text{mit } c' = \frac{1}{c} > 0 \\
	& \Longleftrightarrow & f \ge_{\text{fü}} c' \cdot g \\
	& \Longleftrightarrow & f \in \Omega(g)
\end{eqnarray*}
\begin{eqnarray*}
	g \in \Omega(f) & \Longleftrightarrow & \exists c > 0: g \ge_{\text{fü}} c \cdot f \\
	& \Longleftrightarrow & \frac{1}{c} \cdot g \ge_{\text{fü}} f \\
	& \Longleftrightarrow & c' \cdot g \ge_{\text{fü}} f \quad \text{mit } c' = \frac{1}{c} > 0 \\
	& \Longleftrightarrow & f \le_{\text{fü}} c' \cdot g \\
	& \Longleftrightarrow & f \in \OnotO(g)
\end{eqnarray*}
Ergebnis:
\begin{eqnarray*}
	g \in \OnotO(f) \AND g \in \Omega(f) & \Longrightarrow & g \in \Theta(f) \\
	f \in \OnotO(g) \AND f \in \Omega(g) & \Longrightarrow & f \in \Theta(g)
\end{eqnarray*}
Daraus folgt letztendlich:
$$g \in \Theta(f) \Longrightarrow f \in \Theta(g)$$

\item $g \in \Theta(f) \Longleftarrow f \in \Theta(g)$: \\
analog ($f$ und $g$ vertauschen!)

\item $f \in \Theta(g) \Longrightarrow \OnotO(f) = \OnotO(g)$: \\
$$\left. \begin{array}{c}f \in \Theta(g) \Longrightarrow f \in \OnotO(g) \\ g \in \Theta(f) \Longrightarrow g \in \OnotO(f)\end{array}\right\} \Longrightarrow \OnotO(f) = \OnotO(g) \text{, da } f \in \Theta(g) \Longleftrightarrow g \in \Theta(f)$$

\newpage
\item $f \in \Theta(g) \Longleftarrow \OnotO(f) = \OnotO(g)$: \\
Da $\OnotO(f)=\OnotO(g)$, gilt:
	\begin{itemize}
		\item $f \in \OnotO(g)$
		\item $g \in \OnotO(f)$
	\end{itemize}
Da $f \in \OnotO(g)$ und $g \in \OnotO(f)$ gelten, gilt auch:
	\begin{itemize}
		\item $f \in \Omega(g)$ (ähnliche Rechnung wie vorne)
		\item $g \in \Omega(f)$ (ähnliche Rechnung wie vorne)
	\end{itemize}
Somit gilt:
$$f \in \OnotO(g) \AND f \in \Omega(g) \Longleftrightarrow f \in \Theta(g)$$
und insbesondere:
$$f \in \OnotO(g) \AND f \in \Omega(g) \Longleftarrow f \in \Theta(g)$$
\end{itemize}

\section*{Aufgabe 4}
{\bfseries bearbeitet von Jan Hendrik Dithmar}
\begin{itemize}
	\item $f \in \Theta(g) \Longrightarrow o(f)=o(g)$: \\[0.3cm]
		$f \in \Theta(g) \Longleftrightarrow f \in \OnotO(g) \AND g \in \OnotO(f)$ \\
		Sei $h \in o(f)$, d.h. $\forall c > 0 \exists n_0: h(n) < c \cdot f(n) < cd \cdot g(n)$ mit $d$ aus der Definition von $\OnotO(g)$. \\
		Sei nun $c'>0$ beliebig. Setze $\displaystyle c:=\frac{c'}{d}$. \\
		Somit muss $h \in o(g)$.
	\item $f \in \Theta(g) \Longleftarrow o(f)=o(g)$: analog
\end{itemize}

\end{document}
