\documentclass{bschlangaul-aufgabe}
\bLadePakete{java,mathe}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 2},
  Thematik = {Methoden „matrixSumme()“ und „find()“},
  Referenz = 46115-2016-H.T2-A2,
  RelativerPfad = Examen/46115/2016/09/Thema-2/Aufgabe-2.tex,
  ZitatSchluessel = examen:46115:2016:09,
  ZitatBeschreibung = {Thema 2 Aufgabe 2 (Auszug)},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmische Komplexität (O-Notation)},
  EinzelpruefungsNr = 46115,
  Jahr = 2016,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 2,
}

Geben\index{Algorithmische Komplexität (O-Notation)}
\footcite[Thema 2 Aufgabe 2 (Auszug)]{examen:46115:2016:09} Sie jeweils die kleinste, gerade noch passende Laufzeitkomplexität
folgender Java-Methoden im O-Kalkül (Landau-Notation) in Abhängigkeit
von $n$ und ggf. der Länge der Arrays an.
\footcite[entnommen aus Algorithmen und Datenstrukturen, Übungsblatt 3, Universität Würzburg, Aufgabe 5]{aud:pu:7}

\begin{enumerate}
\item \strut\bigskip

\bJavaExamen[firstline=5,lastline=13]{46115}{2016}{09}{Komplexitaet}

\begin{bAntwort}
Die Laufzeit liegt in $\mathcal{O}(n^2)$.

Begründung (nicht verlangt): Die äußere Schleife wird $n$-mal
durchlaufen. Die innere Schleife wird dann jeweils wieder $n$-mal
durchlaufen. Die Größe des Arrays spielt hier übrigens keine Rolle, da
die Schleifen ohnehin immer nur bis zum Wert $n$ ausgeführt werden.
\end{bAntwort}

\item \strut\bigskip

\bJavaExamen[firstline=15,lastline=25]{46115}{2016}{09}{Komplexitaet}

\begin{bAntwort}
Die Laufzeit liegt in $\mathcal{O}(\log(\text{keys.length}))$. Dabei ist
keys.length die Größe des Arrays bezüglich seiner ersten Dimension.

Begründung (nicht verlangt): Der Grund für diese Laufzeit ist derselbe
wie bei der binären Suche\footcite[Seite 122]{saake}. Die
Größe des Arrays bezüglich seiner zweiten Dimension spielt hier übrigens
keine Rolle, da diese Dimension hier ja nur einen einzigen festen Wert
annimmt.
\end{bAntwort}
\end{enumerate}

\end{document}
