4. GROSSENORDNUNGEN VON FUNKTIONEN

(Landau-Notation)

Die O-Notation (groß-”

O“ Notation):

Wir betrachten zwei Funktionen f(x), g(x) mit x > 0 und Werten

in den reellen Zahlen. Wir schreiben

f(x) = O(g(x)) fur x→∞

falls f(x) fur große Werte von x von der Großenordnung her g(x)

nicht ubersteigt.

”f wachst nicht schneller (bzw. fallt nicht langsamer) als g“.

Mathematisch ausgedruckt:

Es gibt fur die beiden Funktionen eine Konstante c > 0, so dass

|f(x)| ≤ c · |g(x)|

gilt, wenn x nur ausreichend groß ist.

Dahinter steckt die Uberlegung, dass durch Multiplikation mit

einer Konstanten c > 0 eine Funktion in ihrer Großenordnung

unverandert bleibt.

Beispiel: Es gilt 2x + 1 = O(x) fur x→∞,

da 2x + 1 ≤ 3x fur x ≥ 1.

Obige Bedingung ist mit c = 3

fur x ≥ 1 erfullt.

Beispiele: Großenordnungen fur x→∞.

1. 2x3 + 3x2 = O(x3) (betrachte c = 5 und x ≥ 1).

Regel: Bei Potenzen dominieren fur x→∞ die Terme mit den

hochsten Exponenten.

2. x3+xx4−2

= O(x−1) (betrachte c = 4 und x ≥ 2).

3. xm = O(exp(x)) fur jede naturliche Zahl m (betrachte c = m!

und x ≥ 0).

Denn: xm/m! ≤∑∞

n=0 xn/n! = exp(x).

4. ln x = O(x1/m) fur jede naturliche Zahl m.

Ersetze im letzten Beispiel x durch ln x und ziehe die m-te

Wurzel.

5. Ein wichtiger Spezialfall:

f(x) = O(1) bedeutet, dass f(x) fur große x beschrankt bleibt,

dass also |f(x)| ≤ c fur ein c > 0, falls x ausreichend groß ist.

(Hier steht 1 fur die Funktion g, die den festen Wert 1 hat.)

6. z.B.: x+1x = O(1), sin(x) = O(1)

Eine wichtige Rechenregel:

f1(x) = O(g(x)) , f2(x) = O(g(x))

⇒ f1(x) + f2(x) = O(g(x))

Denn aus |f1(x)| ≤ c1|g(x)| und |f2(x)| ≤ c2|g(x)| folgt

|f1(x) + f2(x)| ≤ (c1 + c2)|g(x)|.

Beispiele. x + 2 exp(x) = O(exp(x)), x + ln x = O(x) fur x→∞.

Wir haben gesehen: x = O(exp(x)) und ln x = O(x).

Das gibt aber noch ungenaue Vorstellungen:

exp(x) 2,78 2, 2 · 104 5 · 1011 5 · 1021 2, 7 · 1043 1, 4 · 10217

x 1 10 20 50 100 500ln x 0 2,3 3,0 3,9 4,6 6,2

Die Geschwindigkeit des Wachstums von exp(x), x und ln x ist

hochst unterschiedlich! Um Großenordnungen noch genauer zu

unterscheiden, eine weitere Definition:

Die o-Notation (klein-”

o“ Notation):

Fur zwei Funktionen f(x), g(x), x > 0, schreiben wir

f(x) = o(g(x)) fur x→∞

falls g(x) fur große Werte von x von kleinerer Großenordnung ist

als f(x).

”f entfernt sich weniger schnell von 0, oder geht schneller gegen

0 als g“, kurz

”f ist klein im Vergleich zu g“

Mathematisch ausgedruckt:Gleichgultig, wie man die Konstante c > 0 wahlt, die Ungleichung

|f(x)| ≤ c · |g(x)|ist erfullt, falls x nur ausreichend groß ist.

Beispiel:√

x = o(x) fur x→∞

Fur jedes c > 0 ist cx schließlich großer als√

x.

Wir schreiben auch

f(x)

g(x)→ 0 fur f(x) = o(g(x))

Also:

Wahrend bei f(x) = O(g(x)) die Ungleichung |f(x)| ≤ c · |g(x)|nur fur ein c > 0 erfullt zu sein braucht (das beliebig groß gewahlt

werden darf), muss man bei f(x) = o(g(x)) die Ungleichung fur

alle c > 0 (die dann beliebig klein sein konnen) in Betracht ziehen.

Und in der Sprache der Quantoren:

f(x) = O(g(x)) ⇔ ∃c > 0 ∃x0 ≥ 0 ∀x ≥ x0 : |f(x)| ≤ c · |g(x)|

f(x) = o(g(x)) ⇔ ∀c > 0 ∃x0 ≥ 0 ∀x ≥ x0 : |f(x)| ≤ c · |g(x)|

Beispiele: Großenordnungen fur x→∞

1. xp = o(xq) fur p < q,

denn dann gilt xp/xq = xp−q → 0.

2. xp = o(exp(x)) fur alle reellen Zahlen p,

wegen xp = o(xq) und xq = O(exp(x)) fur p < q.

3. ln x = o(xq) fur alle reellen Zahlen q,

wegen ln x = O(xp) und xp = o(xq) fur p < q.

4. Ein wichtiger Spezialfall:

f(x) = o(1) bedeutet f(x)→ 0, dass also |f(x)| mit wachsen-

dem x kleiner und kleiner wird.

5. z.B.: 1x = o(1), 1

ln x = o(1), ln xx = o(1).

Dieselben Schreibweisen werden benutzt nicht nur fur x → ∞,

sondern auch fur x → x0, also bei Annaherung an eine reelle

Zahl x0. Wir schreiben

f(x) = o(g(x)) fur x→ x0 , fallsf(x)

g(x)→ 0 fur x→ x0

Beispiele von Großenordnungen fur x→ 0:

1. xp = o(xq) fur p > q

denn dann gilt xp/xq = xp−q → 0.

Merke: Fur x → 0 dominieren Potenzen mit kleinerem Expo-

nenten (anders als fur s→∞, wo sich die großeren Exponen-

ten durchsetzen).

2. exp(x) = 1 + o(1),denn exp(x)− 1 = exp(x)− exp(0)→ 0 fur x→ 0.

3. exp(x) = 1 + x + o(x)Dies folgt ausexp(x) =

∑∞n=0 xn/n! = 1 + x + x2

2 + x3

6 + · · · = 1 + x + 0(x2).Graphisch:

o(x)

x