Nach g(n) ∈ O( f (n)) auflösen (O-Notation)

Question

Aufgabe:

Geben Sie mit Begründung/Berechnung an, für welche der folgenden Paare von Funktionen f, g
welche der Eigenschaften f (n) ∈ O(g(n)) und/oder g(n) ∈ O( f (n)) gelten.

Problem/Ansatz:

Wie mache ich weiter?

b) \( f(n)=\frac{n^{2}}{\log n} g(n)=n \cdot(\log n)^{2} \)

\( \lim \limits_{n \rightarrow \infty} \frac{\frac{n^{2}}{\log n}}{n(\log n)^{2}}=\lim \limits_{n \rightarrow \infty} \frac{n^{2} \cdot n(\log n)^{2}}{\log n}=n^{3} \cdot \log n=\infty \)
\( \rightarrow f \notin O(g) \)
\( \lim \limits_{n \rightarrow \infty} \frac{n(\log n)^{2}}{\frac{n^{2}}{\log n}}=\lim \limits_{n \rightarrow \infty} \frac{n(\log n)^{2} \cdot \log n}{n^{2}}=\lim \limits_{n \rightarrow \infty} \frac{(\log n)^{3}}{n} \)

Answer 1

Aloha :)

Im Folgenden wird bei \(\stackrel{(\ast)}=\) die Regel von L'Hospital verwendet:

$$\lim\limits_{n\to\infty}\frac{g(n)}{f(n)}=\lim\limits_{n\to\infty}\frac{n\log^2 n}{\frac{n^2}{\log n}}=\lim\limits_{n\to\infty}\frac{\log^3 n}{n}\stackrel{(\ast)}=\lim\limits_{n\to\infty}\frac{3\log^2 n\cdot\frac{1}{n}}{1}=\lim\limits_{n\to\infty}\frac{3\log^2 n}{n}$$$$\phantom{\lim\limits_{n\to\infty}\frac{g(n)}{f(n)}}\stackrel{(\ast)}=\lim\limits_{n\to\infty}\frac{6\log n\cdot\frac{1}{n}}{1}=\lim\limits_{n\to\infty}\frac{6\log n}{n}\stackrel{(\ast)}=\lim\limits_{n\to\infty}\frac{6\cdot\frac{1}{n}}{1}=\lim\limits_{n\to\infty}\frac{6}{n}=0$$

Also ist \(g(n)\in O(f(n))\).

Comments

wieso ist das , dann   \(g(n)\in O(f(n))\). ?

---

Wenn der Grenzwert null ist, gibt es eine Konstante \(c>0\) und ein \(n_0\in\mathbb N\), sodass für alle \(n\ge n_0\) gilt:$$g(n)<c\cdot f(n)\quad\text{für}\quad n\ge n_0$$

---

vielen dank :)