Das mit dem Limes so zu machen gibt es nur bei der klein O-Natation (\(\mathcal{o}\)). Die kannst du aber auch benutzen, denn wenn \(f\in \mathcal{o} (g)\) gilt, dann gilt auch \(f\in \mathcal{O}(g)\).
Für \(f\in \mathcal{o} (g)\) musst du \(\lim\limits_{n\to \infty}\frac{f(n)}{g(n)} =0\) zeigen.
Dann hast du
\(\frac{f(n)}{g(n)} = \frac{100\cdot n + \log(n)}{n + (\log(n))^2}=\frac{100+\frac{\log(n)}{n}}{1+\frac{(\log(n))^2}{n}}\quad \stackrel{n\to \infty}{\longrightarrow }\quad 100\neq 0\)
Damit gilt schonmal nicht \(f\in \mathcal{o} (g)\).
Bleibt nun die Groß O-Notation.
Dafür gilt diese Definition:
Es sei \(g: \mathbb{N}\rightarrow \mathbb{R}\). Dann ist$$ \mathcal{O}(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ \underbrace{0\leq f(n) \leq \alpha \cdot g(n)}_{0\leq f(n) \ \land f(n)\leq \alpha\cdot g(n) } \} $$
Für \(f\in \mathcal{O} (g)\) musst du per Definition eine Konstante \(\alpha>0\) und eine Stelle \(n_0 \in \mathbb{N}\) angeben, sodass für alle \(n\geq n_0\) die Ungleichung \(0\leq f(n) \leq \alpha \cdot g(n)\) gilt. Entweder sieht man sofort, wie beide Parameter gewählt werden müssen oder du probierst erstmal rum. Ich nehme folgende Abschätzungen vor: Welche Basis hier der Logarithmus annimmt ist vom Prinzip egal. Ich nehme hier mal den 10er-Logarithmus.
\(\begin{aligned}0&<100 \stackrel{n\geq 1}{\leq} f(n)\\&=100\cdot n+\log(n)\\&\leq 100\cdot n+100\cdot \log(n)\\&\stackrel{n\geq 10}{\leq}100\cdot n+100\cdot \log(n)\cdot \log(n)\\&=100\cdot n+100\cdot (\log(n))^2\\&=100\cdot (n+(\log(n))^2)=100\cdot g(n)\end{aligned}\)
Für \(\alpha=100\) und \(n_0=10\) gilt für alle \(n\geq 10\) die Ungleichung
\(0\leq f(n)\leq \alpha\cdot g(n)\), d.h. es gilt \(f\in \mathcal{O}(g)\).
