Was gena ist klein o(n) gegenüber O(n)?
Und Omega(n) und klein omega(n)?

Noch ne frage in Rareys Skript seite 22 Punkt:Rechenregeln für O was soll es das er mal Gross F und mal klein f benutzt?

f ist eine Funktion.
F ist eine Menge von Funktionen.

aa okay sowas haeb ich mir schon gedacht thanx Fred

Was gena ist klein o(n) gegenüber O(n)?
Und Omega(n) und klein omega(n)?

[latex]g(n)=O(f(n)) := \exists c_0 \exists n_0 \forall n > n_0 : g(n) \leq c_0 f(n)[/latex]
g wächst höchstens so schnell wie f (mit irgendwelchen konstanten [latex]c_0, n_0[/latex])

[latex]g(n)=o(f(n)) := \forall c_0 \exists n_0 \forall n > n_0 : g(n) < c_0 f(n)[/latex]
g wächst langsamer als f (für alle konstanten [latex]c_0[/latex] und ein für jedes [latex]c_0[/latex] festes [latex]n_0[/latex])

[latex]g(n) = 10n^2, f(n) = n^2[/latex]:
[latex]g(n) = O(f(n))[/latex], da für [latex]c_0 = 10[/latex] immer [latex]g(n) \leq c_0 f(n)[/latex] gilt. (wegen [latex]10n^2 = 10n^2[/latex])
aber: [latex]g(n) \not= o(f(n))[/latex], da für [latex]c_0 = 3[/latex] [latex]g(n) < c_0 f(n)[/latex] nie (also für kein n) gelten kann (es also auch kein [latex]n_0[/latex] geben kann sodass die ungleichung für alle [latex]n > n_0[/latex] gilt.)

O(log(f(n)^2)exp10qrq(50)) ist die lösung