Hallo :-)
Die formale Definition für die Groß O-Notation lautet in etwa: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) } \}. $$
Analog lässt sich schreiben:
$$ \Omega(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \beta>0 \ \exists n_1 \in \mathbb{N} \ \forall n\geq n_1:\ \underbrace{g(n) \geq \beta \cdot f(n)\geq 0}_{g(n) \geq \beta\cdot f(n) \ \land \beta \cdot f(n)\geq 0 } \}. $$
Damit rechne ich dir mal zwei (je eins wahr und das andere falsch) von den vier Behauptungen vor:
Eins vorab. Ich behandle hier den Logarithmus beispielhaft als den binären Logarithmus, aber das Prinzip bleibt dasselbe.
Zu 2.). Diese Behauptung ist wahr. Das kann man durch folgende Abschätzungskette einsehen:
\( \begin{aligned}0&\stackrel{n\geq 1}{\leq} 3 \cdot n+2\cdot \log(n)\\[15pt]&\stackrel{n\geq 2}{\leq} 3 \cdot n\cdot \log(n)+2\cdot \log(n)\\[15pt]&\stackrel{n\geq 2}{\leq} 3 \cdot n\cdot \log(n)+2\cdot \log(n)\cdot n\\[15pt]&=5\cdot n \cdot \log(n) \end{aligned}\)
Also gilt mit \(n_0=2\) und \(\alpha=5\) die Eigenschaft
\( 3 n+2 \log n \in \mathcal{O}(n \cdot \log n) \).
Zu 1.). Diese Behauptung ist falsch. Sicher kennst du diese Beziehung:
\(f\in \mathcal{O}(g) \Leftrightarrow g\in \Omega(f)\), die man aber sehr schnell mit der Definition zeigen kann: (kurz)
\(f\in \mathcal{O}(g) \Leftrightarrow 0\leq f(n) \leq \alpha \cdot g(n) \stackrel{\alpha>0}{\Leftrightarrow} 0\leq \underbrace{\frac{1}{\alpha}}_{=:\beta} \cdot f(n) \leq g(n) \Leftrightarrow g\in \Omega(f)\).
Also gilt ja auch dadurch \(f\notin \mathcal{O}(g) \Leftrightarrow g\notin \Omega(f)\).
Damit zeige ich also, dass \(\underbrace{2\cdot n^2}_{=:g(n)} \notin \Omega\left(\underbrace{\frac{n^4}{\log(n+2)}}_{=:f(n)}\right)\).
Dafür negiert man die Omega-Definition:
\(g\notin \Omega(f) \Leftrightarrow \quad \forall \beta>0\ \forall n_1\in \mathbb{N}\ \exists n\geq n_1: \ \underbrace{g(n) < \beta\cdot f(n)}_{(1)} \ \lor \underbrace{\beta \cdot f(n) < 0}_{(2)} \)
Teil (2) ist beim Betrachten immer falsch, sodass (1) gezeigt werden muss, damit diese Oder-Aussage wahr ist. Jetzt ist Basteln angesagt. Es soll also in Abhängigkeit von \(\beta\) und \(n_1\) ein \(n\geq n_1\) gefunden werden, sodass
\(2\cdot n^2=g(n) < \beta\cdot f(n)=\beta\cdot \frac{n^4}{\log(n+2)}\)
gilt. Jetzt probiert man halt so paar Sachen aus:
Statt \(2\cdot n^2 < \beta\cdot \frac{n^4}{\log(n+2)}\)
betrachte ich mal zb
\(2< \beta\cdot \frac{n^2}{\log(n+2)}\)
und damit betrachte ich
\(2< \beta\cdot n\)
und damit \(\frac{2}{\beta}<n\). Mit \(\frac{2}{\beta}<n\) könnte man arbeiten. Ich fordere also, dass \(\frac{2}{\beta}<n\) gilt. Dann habe ich
\(\frac{2}{\beta}<n \stackrel{n\leq 2}{\leq} n\cdot \underbrace{\frac{n}{\log(n+2)}}_{\geq 1}\).
Jetzt muss noch \(n_1\) ins Spiel kommen.
Dafür fordere ich nun als Ergebnis \(n>\max\left(n_1,2,\frac{2}{\beta}\right)\).
Damit hat man also
\(\begin{aligned}&\frac{2}{\beta}<n\leq n\cdot \frac{n}{\log(n+2)}=\frac{n^2}{\log(n+2)} \\&\Leftrightarrow \frac{2}{\beta}\cdot n^2 < \frac{n^4}{\log(n+2)} \\&\Leftrightarrow 2\cdot n^2 <\beta\cdot \frac{n^4}{\log(n+2)}\end{aligned}\)
Und genau das wahr zu zeigen.
