\documentclass{bschlangaul-aufgabe}
\bLadePakete{syntax,mathe}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 6},
  Thematik = {Sortieren von O-Klassen},
  Referenz = 66115-2019-H.T1-A6,
  RelativerPfad = Examen/66115/2019/09/Thema-1/Aufgabe-6.tex,
  ZitatSchluessel = examen:66115:2019:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmische Komplexität (O-Notation), Master-Theorem},
  EinzelpruefungsNr = 66115,
  Jahr = 2019,
  Monat = 09,
  ThemaNr = 1,
  AufgabeNr = 6,
}

\begin{enumerate}

%%
% (a)
%%

\item Sortieren\index{Algorithmische Komplexität (O-Notation)}
\footcite{examen:66115:2019:09} Sie die unten angegebenen Funktionen der
O-Klassen $\mathcal{O}(a(n))$, $\mathcal{O}(b(n))$, $\mathcal{O}(c(n))$,
$\mathcal{O}(d(n))$ und $\mathcal{O}(e(n))$ bezüglich ihrer
Teilmengenbeziehungen. Nutzen Sie ausschließlich die echte Teilmenge
$\subset$ sowie die Gleichheit $=$ für die Beziehung zwischen den
Mengen. Folgendes Beispiel illustriert diese Schreibweise für einige
Funktionen $f_1$ bis $f_5$ (diese haben nichts mit den unten angegebenen
Funktionen zu tun):
\bFussnoteUrl{http://www.s-inf.de/Skripte/DaStru.2012-SS-Katoen.(KK).Klausur1MitLoesung.pdf}

\begin{displaymath}
\mathcal{O}(f_4 (n)) \subset \mathcal{O}(f_3(n)) = \mathcal{O}(f_5(n)) \subset \mathcal{O}(f_1(n)) = \mathcal{O}(f_2(n))
\end{displaymath}

Die angegebenen Beziehungen müssen weder bewiesen noch begründet werden.

\begin{itemize}
\item $a(n) = n^2 \cdot \log_2(n) + 42$
\item $b(n) = 2^n + n^4$
\item $c(n) = 2^{2 \cdot n}$
\item $d(n) = 2^{n+3}$
\item $e(n) = \sqrt{n^5}$
\end{itemize}

\begin{bAntwort}
\begin{align*}
a(n) &= n^2 \cdot \log_2(n) + 42 &&= n\\
b(n) &= 2^n + n^4 &&= 2^n\\
c(n) &= 2^{2 \cdot n} &&=2^{2 \cdot n}\\
d(n) &= 2^{n+3} &&= 2^n\\
e(n) &= \sqrt{n^5}\\
\end{align*}

\begin{displaymath}
\mathcal{O}(a (n)) \subset \mathcal{O}(e(n)) \subset \mathcal{O}(b(n)) = \mathcal{O}(d(n)) \subset \mathcal{O}(c(n))
\end{displaymath}

\begin{displaymath}
\mathcal{O}(n^2 \cdot \log_2(n) + 42) \subset
\mathcal{O}(\sqrt{n^5}) \subset
\mathcal{O}(2^n + n^4) =
\mathcal{O}(2^{n+3}) \subset
\mathcal{O}(2^{2 \cdot n})
\end{displaymath}
\end{bAntwort}

%%
% (b)
%%

\item Beweisen Sie die folgenden Aussagen formal nach den Definitionen
der O-Notation oder widerlegen Sie sie.

\begin{enumerate}

%%
% (i)
%%

\item $\mathcal{O}(n \cdot \log_2 n) \subseteq \mathcal{O}(n \cdot (\log_2 n)^2)$

\begin{bAntwort}
Die Aussage gilt.
Für $n \geq 16$ haben wir
\begin{displaymath}
(\log_2 n)^2 \leq n \Leftrightarrow \log_2 n  \leq \sqrt n
\end{displaymath}

und dies ist eine wahre Aussage für $n \geq 16$. Also gilt die Aussage mit $n_0 = 16$ und $c = 1$.
\end{bAntwort}

%%
% (ii)
%%

\item $2^{(n+1)} \in \mathcal{O}(n \cdot \log_2 n)$
\end{enumerate}

%%
% (c)
%%

\item Bestimmen Sie eine asymptotische Lösung (in $\Theta$-Schreibweise)
für die folgende Rekursionsgleichung:
\index{Master-Theorem}

\begin{enumerate}

%%
% (i)
%%

\item $T(n) = 4 \cdot T(\frac{n}{2}) + n^2$

%%
% (ii)
%%

\item $T(n) =  T(\frac{n}{2}) +\frac{n}{2} n^2 + n$
\end{enumerate}

\end{enumerate}

\end{document}