Forum: PC-Programmierung O Notation - Ist O(n) + O(log n) = O(n)?


von LL0rd (Gast)


Lesenswert?

Hallo Leute,

eben nur ganz kurz eine Frage: Ist O(n) + O(log n) = O(n) ?

von Εrnst B. (ernst)


Lesenswert?

Ja.

von LL0rd (Gast)


Lesenswert?

Dankeschön!

von Rolf (Gast)


Lesenswert?

D.h. O(log(n)=0 oder was?

von Chris (Gast)


Lesenswert?

Nein, O(f(n)) ist eine Menge. Und + bedeutet bei Mengen üblicherweise 
"Vereinigung".

O(n) + O(log n) ist also die Vereinigung der Mengen O(n) und O(log n). 
Und da O(log n) nur eine Teilmenge von O(n) ist, ist die Vereinigung 
genau O(n).

von Εrnst B. (ernst)


Lesenswert?

Und weils grad so schön ist, nehmen wir das Mooresche Gesetz als gegeben 
an, und beweisen O(2^n)=O(n). ;)

von yalu (Gast)


Lesenswert?

@Ernst Bachmann:

Da du ein Freund des großen O zu sein scheinst: Bist du vielleicht ein
Nachfahre vom Paul, der diese Notation lt. Wikipedia als erster
verwendet hat?

  http://de.wikipedia.org/wiki/Paul_Bachmann_(Mathematiker%29

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.