Hallo :-)
Die Definition der O-Notation lautet ja in etwa so:
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\in \N_{\geq n_0}:0\leq f(n) \leq \alpha \cdot g(n) \} $$
die Menge aller Funktion \(f\), die bis auf eine Konstante \(\alpha>0\) höchstens so schnell wächst wie \(g\).
Zu a). Du musst also für alle \(\varepsilon>0\) ein \(\alpha>0 \) und ein \(n_0\in \mathbb{N}\) so angeben, sodass nachweislich für alle \(n\geq n_0\) diese Abschätzung gilt: \(0\leq f(n) \leq \alpha \cdot g(n)\), konkreter hier: \(0\leq n\cdot \ln(n)\leq \alpha\cdot n^{1+\varepsilon}=\alpha\cdot n\cdot n^{\varepsilon}\).
Nebenrechnungen:
Stattdessen untersuche ich zuerst die Ungleichung \(0\leq \ln(n)\leq \alpha\cdot n^{\varepsilon}\) auf die oben genannten Quantoreneigenschaften, also ob es mir hier gelingt, für alle \(\varepsilon>0\) ein \(\alpha>0 \) und ein \(n_0\in \mathbb{N}\) so anzugeben, sodass nachweislich für alle \(n\geq n_0\) eben diese Abschätzungskette gilt. Die Forme ich jetzt mal etwas um:
Schonmal die erste Wahl für den Startindex \(n_0\), nämlich \(n_0=1\).
$$ 0\leq \ln(n)\leq \alpha\cdot n^{\varepsilon} \quad \stackrel{\alpha >0}{\Longleftrightarrow} \quad 0\leq \frac{1}{\alpha}\cdot \ln(n)\leq n^{\varepsilon} \quad \stackrel{\alpha >0}{\Longleftrightarrow} \quad 0\leq \ln\left ( n^{\frac{1}{\alpha}}\right)\leq n^{\varepsilon}.\quad (*)$$
Außerdem gilt für alle \(x\in \R_{>0}\) stets \(\ln(x)\leq x\). Also wähle ich \(\alpha=\frac{1}{\varepsilon}\), sodass die Ungleichung (*) erfüllt ist.
Nebenrechnungen Ende
Und jetzt habe ich alles, was ich brauche, um den finalen Beweis aufzuschreiben:
Beweis: Sei \(\varepsilon>0\) beliebig, wähle \(\alpha>0\) durch \(\alpha=\frac{1}{\varepsilon}\) und sei \(n_0=1\). Dann gilt für alle \(n\in \N_{\geq 1}\)
$$ 0\leq \varepsilon \cdot \ln(n)=\ln\left (n^{\varepsilon}\right)\leq n^{\varepsilon} \quad \stackrel{\varepsilon>0}{\Longrightarrow} \quad 0\leq \ln(n)\leq \frac{1}{\varepsilon}\cdot n^{\varepsilon}=\alpha \cdot n^{\varepsilon}\\\quad \stackrel{n\geq 1}{\Longrightarrow} \quad 0\leq n\cdot \ln(n)\leq \alpha \cdot n\cdot n^{\varepsilon}=\alpha \cdot n^{1+\varepsilon}.$$
Zu b). Ist falsch. Betrachte als Beispiel \(f(n)=2n\) und \(g(n)=n\). Mit der obigen Definition kannst du zeigen, dass erstmal \(f(n)\in \mathcal{O}(g(n))\) gilt, aber \(2^{f(n)}=2^{2\cdot n}=(2^2)^n=4^n\notin \mathcal{O}(2^n)=\mathcal{O}(2^{g(n)})\).
