TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 3

Beweisen Sie, dass für die im Folgenden definierte Funktion $f(n)$ die Beziehung $f(n)=O(n^{2})$ gilt.

Verwenden Sie für Ihren Beweis die Konstante $c=2$ und wählen Sie den kleinstmöglichen Wert für $n_{0}$.

$f(n)=\left\{{\begin{array}{l l}n^{2}+23n,&falls~n~>~10\\n^{3}~log~n+n&sonst\\\end{array}}\right.$

Lösung

Beweis

f(n) = O(Fehler beim Parsen (⧼math_empty_tex⧽): {\displaystyle } )

Tabelle

Kreuzen Sie anschließend die folgenden Tabelle die zutreffenden Felder an:

${\begin{array}{| c | c | c | c | c |}\hline f(n){\text{ ist}}&\Theta (.)&O(.)&\Omega (.)&{\text{keines}}\\\hline \hline n{\sqrt {n}}&&&X&\\\hline n^{3}&&X&&\\\hline n~log~n^{n}&&X&&\\\hline \end{array}}$