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 :)