Landau Symbole (Big-Oh-Notation)

Ich weiß, dass bei einer Laufzeit von z.B. 3n^4 + 2n² + 14n man einfach O(n^4) schreib. Jetzt will ich allerdings auch genau wissen wieso.

Auf dieser http://img129.imageshack.us/my.php?image=landau0he.jpg Rechner steht glaube ich die Lösung.
Leider verstehe ich die Rechnung noch nicht ganz. Deshalb meine Fragen:

Gehe ich recht in der Annahme, dass in dieser Rechnung ein beliebiges Polynom f(n) zerlegt wird in C*n^k (also eine konstante C und das n mit dem höchsten Exponent)?
Wieso wird in der zweiten Zeile aus dem = ein <= ?
Meine entscheidende Frage: Wieso fallen von Zeile3 auf Zeile4 einfach die ganzen Brüche $\frac{1}{n},\frac{1}{n^2}$ usw. einfach weg?

Daniel E.

Guck dir an, was man mit der Notation eigentlich erreichen will und wie sie definiert ist. http://de.wikipedia.org/wiki/Landau-Symbol

ich weiß was sie erreichen will und wie sie definiert ist. ich verstehe die rechung dennoch nicht (besonders frage 3))

Daniel E.

landauer schrieb:

ich weiß was sie erreichen will und wie sie definiert ist. ich verstehe die rechung dennoch nicht (besonders frage 3))

Ist aber doch klar: n ist aus N, also ist jedes n >= 1, also ist 1/n <= 1 für alle n. Analog für alle höheren Potenzen. Also ist jeder Summand a_i/n^i <= a_i, also darf man so abschätzen.

ein algo (oder funktion f(n)) ist O(n^4), wenn es eine konstante $c$ gibt, so dass $f(n) \le c \cdot n^4$ für alle $n$ größer als ein bestimmtes $n_0$ .
in deinem fall kannst du also z.b. $c = 6$ und $n_0 = 2$ wählen. ganz einfach. (das ist die einfachere definition, siehe wikipedia, dritte tabelle.)

zu den fragen

es wird nicht zerlegt, sondern nach oben abgeschätzt. wahrscheinlich meintest du das, ist aber ein unterschied.
ich glaube, das war ein versehen. ich sehe zumindest auf den ersten blick nichts wo das herkommen könnte.
die fallen nicht weg: der schätzt einfach jeden summanden der form |bla|*1/n durch |bla| ab, weil |bla|*1/n <= |bla| für alle n > 0 ist.