Algorithmen und Datenstrukturen

Welche Formel bestimmt die Vergleichsrelationen?

O-Notation:
Gegebene Funktion n³ <= Beweis (- wird weggelassen, höchster Exponent zählt)
Mit n0 = 1, c = 23 gilt also f(n) € O(n³)
 
Ω-Notation:
Gegebene Funktion n³ >= Beweis (- wird weggelassen, höchster Exponent zählt)
Mit n0 = 1, c = 23 gilt also f(n) € O(n³)
 
Somit gilt f(n) € θ(n³) (n³ wächst asymptotisch wie f)
 

Diskussion