Klein-o-Notation: Wie beweisen?

Question

Aufgabe:

Bitte beachten, dass hier r = 4 ist.

Problem/Ansatz:

Kann mir hier jemand schnell weiterhelfen? Ich weiß, dass ich hier zeigen muss, dass folgendes gilt:

Ist mein Ansatz so richtig?

(i) (4+1)n^2 / n^3 + n^2 + 5

(ii) 5n^2 / n^3 + n^2 + 5

(iii) (n^2 * 5) / n^3 / (1 + (n^2 / n^3) + 5/n^3)

(vi) ((1 * 5) / n) / (1 + (1 / n) + 5/n)

(v) (5 /n) / (1 + (1 / n) + 5/n)

(vi) 1 / (1 + (1 / n) = 1 / 1 + 0 = 1 / 1 = 1

Somit gilt die Aussage NICHT


Falls es falsch ist, kann mir jemand bitte die Lösung richtig stellen, damit ich es dann besser nachvollziehen kann, wo denn hier der Fehler liegt, dafür bekommt ihr von mir ewige Dankbarkeit geschenkt. （︶^︶）

Answer 1

Aloha :)

Kürze Zähler und Nenner mit \(n^2\):$$\frac{g(n)}{f(n)}=\frac{5n^2}{n^3+n^2+5}=\frac{\frac{1}{n^2}\cdot5n^2}{\frac{1}{n^2}\cdot\left(n^3+n^2+5\right)}=\frac{5}{n+1+\frac{5}{n^2}}$$Ein Bruch wird größer, wenn man seinen Nenner verkleinert:$$\frac{g(n)}{f(n)}=\frac{5}{n+1+\frac{5}{n^2}}<\frac{5}{n}\to0$$Die Aussage gilt also: \(g(n)\in o(f(n))\)

Comments

Ich glaube du meinst am Ende die o-Notation und nicht die O-Notation, denn es gibt auch Fälle, bei dem trotz \(g(n)\in \mathcal{O}(f(n))\) nicht \(\lim\limits_{n\to \infty} \frac{g(n)}{f(n)}=0\) gilt, zb mit \(g(n)=n\) und \(f(n)=2n\).

Weil hier nun aber \(\lim\limits_{n\to \infty} \frac{g(n)}{f(n)}=0\) gilt, lässt sich tatsächlich \(g(n)\in o(f(n))\) folgern, sodass erst recht \(g(n)\in \mathcal{O}(f(n))\) gilt.

---

Danke für den Hinweis.

Ich meinte natürlich die Klein-o-Notation.

Für Groß-O muss der Grenzwert lediglich existieren.

Für Klein-o muss er Null sein.

Ich habe das noch verbessert ;)

---

Oh, vielen vielen Dank! Geheiligt seist Du!!! ^~^

Aber ich habe da noch eine kleine Frage, wie hast Du denn Nenner dort gekürzt, sodass nur noch 5 / n übrig bleibt? :0

---

Ich habe im Nenner gar nicht gekürzt. Ich habe den Nenner kleiner gemacht. Dadurch wird der Bruch größer und ich kann den Bruch nach oben abschätzen:

$$n+1+\frac{5}{n^2}>n\implies\frac{1}{n+1+\frac{5}{n^2}}<\frac{1}{n}\implies\frac{5}{n+1+\frac{5}{n^2}}<\frac{5}{n}$$

---

Aso, ja dann ist alles klar. Ich Danke Dir für Deine tolle Erklärung sowie Unterstützung! ヾ(^▽^*)))