Landau-Symbole: ƒ(n) = 3n^3 + 2n^2 + n. Zeige, dass ƒ ∈ O(n^3).

Question

Aufgabe:

Sei ƒ(n) = 3n³ + 2n² + n

Problem/Ansatz:

Zeiht oder widerlegt: ƒ ∈ O(n³)

Answer 1

Hallo,

\(f\in \mathcal{O}(n^3)\) gilt genau dann, falls zwei Konstanten \(c>0\) und \(N\in \mathbb{N}\) existieren, so dass für alle \(n\geq N\) gilt, dass \(f(n)\leq c\cdot n^3\). Sprich: \(f\) wächst nicht wesentlich schneller als \(n^3\).

Es gilt:$$\frac{3n^3+2n^2+n}{n^3}=3+\frac{2}{n}+\frac{1}{n^2}\leq 3+\frac{2}{1}+\frac{1}{1}=6$$$$\Longrightarrow 3n^3+2n^2+n\leq 6\cdot n^3$$ für alle \(n\geq 1\).

Manchmal muss man noch zeigen, dass \(f\notin \mathcal{O}(n^2)\) ... also die Minimalität - das würde ich nochmal nachsehen.

Comments

vielen dank!

Ich habe noch eine kleine Aufgabe die ich nicht verstanden habe. Vielleicht wissen sie wie man das lösen kann?

Sei g : N → N eine Funktion. Definiert formal: O(g) und Ω(g)

---

Das kann man durch Recherche erledigen. Das hättest du eigentlich vor dieser Frage tun sollen.