Regeln für O-Kalküle mit Potenzen

Question

eine Kurze Frage zu den Regeln für Kalküle.

f(n)^l = Ο(f(n)^k)

Ist damit zum Beispiel so etwas gemeint.

n^3 = O(n^4)  oder log(n)^4 = Ο(n^5)

lg

Comments

Es gibt keine "Regeln für Kalküle". Und f(n)^l = Ο(f(n)^k) ist ohne weitere Angaben zu f, l und k einfach falsch.

---

Schau mal bei den Landau-Symbolen https://de.wikipedia.org/wiki/Landau-Symbole und dann v.a. in deine Unterlagen. Wenn du auf Wikipedia die Sprache umstellst auf z.B. Englisch, Französisch,usw., findest du verschiedene vorgerechnete Beispiele.

---

Sei : N → R
 mit f(n)   ≥ 1 für alle .
Weiter sei k,l  ≥ 0 mit k ≥ l. Dann gilt:

Das habe ich vergessen dazu zu schreiben. Dann müssten die Aufgaben stimmen oder?

---

EDIT: Wo steht das denn genau in der Frage? Bitte vollständige Frage im nächsten Kommentar.

Answer 1

> n³ = O(n⁴)

Ja, dass ist mit f(n)^l = Ο(f(n)^k) gemeint. Aber auch

    n⁴ = O(n³)

ist damit gemein. Letzteres ist natürlich falsch.

> log(n)⁴ = Ο(n⁵)

Überleg mal, was hier f(n) ist. Im ersten Beispiel war f(n) = n.