Für beliebige Funktionen f,g gilt:
Als erstes machen wir den Beweis nach rechts ( )
nun der Beweis nach links ( )
1.
2.
3.
Beweis zu 1. nach rechts ( )
Beweis zu 1. nach links ( )
(siehe Definition)
und sei t(n) ein beliebiges Element der Menge O(f(n))
(siehe Definition)
(Definition der Teilmenge, da t(n) ein beliebiges Element ist)
Damit ist
Damit ist
Damit ist
Falls , dann ist auch .
Dabei ist eine Konstante.
Gibt es immer eine Ordnung zwischen den Funktionen? Es gibt Funktionen f und g mit . Ein Beispiel sind die Funktionen sin(n) und cos(n).
Für alle
Wir nehmen an, dass ,
das heißt .
Aber es muss auch gelten,
das heißt