Transitivitaet der Landau-Notation.

[Michael G. (linuxgeek)]

Hallo Forum,

hier mal eine mathematische Problemstellung. Wahrscheinlich kennt Ihr ja 
die Landau-Notation:

$$f \in \mathcal{O}(g)$$

wobei man hier mit der asymptotischen oberen Schranke arbeit, so dass 
fuer obige Aussage gelten muss:

$$0 \le \limsup_{x \to a} \left|\frac{f(x)}{g(x)}\right| < \infty$$

Das heisst f ist in der Ordnung von g, falls der asymptotische Grenzwert 
definiert ist.

Die Operation ist transitiv, d.h.

$$f(n) = \mathcal{O}(g(n)) \and g(n) = \mathcal{O}(h(n)) \Rightarrow f(n) = \mathcal{O}(h(n))$$

Wie koennte man dies am besten beweisen? Kommt man da mit den 
Rechenregeln des Limes hin mit oder sollte man einen konstruktiveren 
Ansatz waehlen?

Ich bitte um konstruktive Vorschlaege... ;)

Gruss,
Michael

[Jörg (Gast)]

Vergiss die math. Äquivalenz zum "0 <= lim sup |..|<.." und betrachte
die Definition des Landau-Symbols O(f): es ex. ein C,Epsilon so dass..
(z.B. auf Wikipedia). Du erhältst zur linken Seite deiner Behauptung
ein C1,Eps1 für f=O(g) und ein C2,Eps2  für g=O(h). Damit bastelst du
dir einfach ein C3,Eps3 so dass f=O(h).

Gruss

Jörg

[Katapulski (Gast)]

Alle Achtung! Was es nicht alles gibt...

IKSLUPATAK ist die umgekehrte Notation  von Katapulski.

gez. Katapulski

[klodeckel (Gast)]

ja, ich bin auch zutiefst beeindruckt.

guude

ts

[Menschenkenner (Gast)]

Mein Gott, ist das löten einer Platine so banal...ich schäme mich für 
mein Präkariaten dasein.

[Bernd G. (Gast)]

Was ist eigentlich aus den transitiven Hüllen geworden?
Beitrag "praktische Informatik (transitive Hülle)"

[Jango (Gast)]

> ja, ich bin auch zutiefst beeindruckt.

Ich nicht. Ist doch nur Informatik Grundstudium :-)