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.
1.
2.
Ein häufiges Problem sind Grenzwerte der Art oder
Bei diesem Problem kann man als Ansatz die Regel von de l'Hospital verwenden.
Satz(Regel von de L'Hospital)
Seien f und g auf dem Intervall differenzierbar.
Es gelte
und es existiere .
Dann existiert auch und es gilt:
1.
-
2.
-
Beim zweiten Beispiel musste die Regel von de l'Hospital wiederholt angewandt werden.
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