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)=\{\begin{array}{cc}{n}^2+23n,& fallsn>10\\ n^{3}logn+n& sonst\end{array}$

Lösung

Beweis

f(n) = O(${\displaystyle }$)

Tabelle

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

$\begin{array}{ccccc}f(n)\text{ ist}& \Theta (.)& O(.)& \Omega (.)& \text{keines}\\ \text{HLINE TBD}n\sqrt{n}& & & X& \\ n^3& & X& & \\ nlog{n}^n& & X& & \end{array}$