O-Notation:
Seien f,g: N -> R+ Funktionen. Wir definieren:
O(f) = {g | $ c > 0, n0 > 0 : g(n) <= c f(n) " n >= n0}
In Worten: Die Funktion g ist von der Ordnung f, wenn für alle n> n0 eine positive Konstante c existiert, so dass g(n) <= c f(n) gilt, d.h. dass die Funktion g durch die Funktion cf majorisiert wird. Die Funktionen f und g seien beide nicht negativ.
3n4 + 5n3 + 7 log n ? O(n4), denn
3n4 + 5n3 + 7 log n < 3n4 + 5n4 + 7n4 = 15 n4 für n >= 1.
Wähle also c = 15, n0 = 1.
In O(n4) steht n4 für die Funktion, die n auf n4 abbildet.
Häufig schreibt man auch h = O(n4) statt h Î O(n4)
O macht Abschätzung nach oben, nach unten: W
W(f) = {g | $ c > 0 , n0 > 0 : g(n) >= cf(n) " n>= n0 }