\documentclass{bschlangaul-aufgabe}
\bLadePakete{mathe}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4: Komplexität},
  Thematik = {limes},
  Referenz = 66115-2012-H.T2-A6,
  RelativerPfad = Examen/66115/2012/09/Thema-2/Aufgabe-6.tex,
  ZitatSchluessel = examen:66115:2012:09,
  ZitatBeschreibung = {Aufgabe 6},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmische Komplexität (O-Notation)},
  EinzelpruefungsNr = 66115,
  Jahr = 2012,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 6,
}

Gegeben seien die Funktionen $f \colon \mathbb{N} \rightarrow
\mathbb{N}$ und $g \colon \mathbb{N} \rightarrow \mathbb{N}$, wobei $f
(n) = (n - 1)^3$ und $g(n) = (2n + 3)(3n + 2)$. Geben Sie an, welche der
folgenden Aussagen gelten. Beweisen Sie Ihre
Angaben.\index{Algorithmische Komplexität (O-Notation)}
\footcite[Aufgabe 6]{examen:66115:2012:09}

\footcite[Aufgabe 4]{aud:ab:2}
\begin{enumerate}
\item $f(n) \in \mathcal{O}(g(n))$
\item $g(n) \in \mathcal{O}(f(n))$
\end{enumerate}

\begin{bExkurs}[Regel von L’Hospital]
Die Regel von de L’Hospital ist ein Hilfsmittel zum Berechnen von
Grenzwerten bei Brüchen $\frac{f}{g}$ von Funktionen $f$ und $g$, wenn
Zähler und Nenner entweder beide gegen $0$ oder beide gegen (+ oder -)
unendlich gehen. Wenn in einem solchen Fall auch der Grenzwert des
Bruches der Ableitungen existiert, so hat dieser denselben Wert wie der
ursprüngliche Grenzwert:
\footnote{\url{https://de.serlo.org/mathe/funktionen/grenzwerte-stetigkeit-differenzierbarkeit/grenzwert/regel-l-hospital}}

\begin{displaymath}
\lim_{x \to x_0} \frac{f(x)}{g(x)} = \lim_{x \to x_0} \frac{f'(x)}{g'(x)}
\end{displaymath}

\end{bExkurs}

\begin{bAntwort}
Es gilt Aussage (b), da $f(n) \in \mathcal{O}(n^3)$ und $g(n) \in
\mathcal{O}(n^2)$ und der Grenzwert $\lim$ bei größer werdendem $n$
gegen $0$ geht. Damit wächst $f(n)$ stärker als $g(n)$, sodass nur
Aussage (b) gilt und nicht (a). Dafür nutzen wir die formale Definition
des $\mathcal{O}$-Kalküls, indem wir den Grenzwert $\frac{f}{g}$ bzw.
$\frac{g}{f}$ bilden:

{
\footnotesize
\begin{displaymath}
\lim_{n \to \infty}
\frac{f(n)}
{g(n)}
=
\lim_{n \to \infty}
\frac{(n - 1)^3}
{(2n + 3)(3n + 2)}
=
\lim_{n \to \infty}
\frac{3(n - 1)^2}
{(2n + 3) \cdot 3 + 2 \cdot (3n + 2)}
=
\lim_{n \to \infty}
\frac{6(n - 1)}
{12}
=
\infty
\end{displaymath}

\begin{displaymath}
\lim_{n \to \infty}
\frac{g(n)}
{f(n)}
=
\lim_{n \to \infty}
\frac{(2n + 3)(3n + 2)}
{(n - 1)^3}
=
\lim_{n \to \infty}
\frac{(2n + 3) \cdot 3 + 2 \cdot (3n + 2)}
{3(n - 1)^2}
=
\lim_{n \to \infty}
\frac{12}
{6(n - 1)}
=
0
\end{displaymath}
}
Hinweis: Hierbei haben wir bei die Regel von L’Hospital angewendet.
\end{bAntwort}

\end{document}