Da musst du auch nur wieder die Definitionen nachprüfen:
Es sei \(g: \mathbb{N}\rightarrow \mathbb{R}\).
$$1.)\quad \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) \text{ und } f(n)\leq \alpha\cdot g(n) } \} $$
$$2.)\quad \Omega(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \beta>0 \ \exists n_1 \in \mathbb{N} \ \forall n\geq n_1:\ \underbrace{0\leq \beta \cdot g(n) \leq f(n)}_{0\leq \beta\cdot g(n) \text{ und } \beta\cdot g(n)\leq f(n) } \} $$
$$3.)\quad \Theta(g):=\mathcal{O}(g)\cap \Omega(g)$$
Zu 1.). Finde also ein \(\alpha>0\) und eine Stelle \(n_0\in\mathbb{N}\), sodass für alle \(n\geq n_0\) die Ungleichung \(0\leq n\cdot \log_3(n^2)\leq \alpha\cdot n\cdot (\log_3(n))^2\) gilt. Diese Parameter kann man beim bloßen Versuch der Abschätzung einsehen:
\(0\stackrel{n\geq 1}{\leq} \log_3(n)\)
Daraus folgt
$$0\stackrel{n\geq 1}{\leq} n\cdot \log_3(n^2)=2\cdot n\cdot \underbrace{\log_3(n)}_{\geq 1,\space \forall n\geq 3}\stackrel{n\geq 3}{\leq }2\cdot n\cdot \log_3(n)\cdot \log_3(n)=2\cdot n\cdot (\log_3(n))^2$$
Also gilt mit \(\alpha=2\) und \(n_0=3\) für alle \(n\geq 3\) die Abschätzung
\(0\leq n\cdot \log_3(n^2)\leq \alpha\cdot n\cdot (\log_3(n))^2\),
sodass \(n\cdot \log_3(n^2)\in \mathcal{O}(n\cdot (\log_3(n))^2)\) gilt.
Zu 2.). Diese Aussage ist falsch. Um das zu zeigen, muss man also die Aussage
\(n\cdot \log_3(n^2)\notin \Omega(n\cdot (\log_3(n))^2)\) betrachten. In Quantorenschreibweise sieht das so aus:
$$ \forall \beta>0 \ \forall n_1 \in \mathbb{N} \ \exists n\geq n_1:\ \underbrace{0> \beta\cdot n\cdot (\log_3(n))^2}_{(1)} \text{ oder } \underbrace{\beta\cdot n\cdot (\log_3(n))^2> n\cdot \log_3(n^2)}_{(2)} $$
(1) ist offensichtlich immer falsch.
Also muss man (2) zeigen, sodass diese Oder-Aussage wahr ist. Finde also in Abhängigkeit von \(\beta>0\) und \(n_0\in \mathbb{N}\) ein \(n\geq n_0\), sodass Abschätzung (2) gilt.
Dafür probiert man etwas rum:
\(\beta\cdot n\cdot (\log_3(n))^2> n\cdot \log_3(n^2)\).
Zu kompliziert. Ich betrachte stattdessen:
\(\beta\cdot (\log_3(n))^2> \log_3(n^2)=2\cdot \log_3(n)\).
Immernoch zu kompliziert. Also:
\(\beta\cdot \log_3(n)> 2\) bzw. \(\log_3(n)>\frac{2}{\beta}\) bzw. \(n>3^{\frac{2}{\beta}}\)
Das letzte sieht sehr vielversprechend aus. Um jetzt noch \(\beta>0\) und \(n_0\in \mathbb{N}\) ins Boot zu holen, wähle ich mein finales \(n\in \mathbb{N}\) folgendermaßen:
\(n>\max\left(\beta, n_0,3^{\frac{2}{\beta}}\right)\). Dann ist \(n>n_0\) und \(n>3^{\frac{2}{\beta}}\). Also hat man:
$$\begin{aligned}n&>3^{\frac{2}{\beta}}>1\\[10pt]&\Leftrightarrow \log_3(n)>\frac{2}{\beta}\\[10pt]&\Leftrightarrow \beta\cdot \log_3(n)>2\\[10pt]&\Leftrightarrow \beta\cdot (\log_3(n))^2>2\cdot \log_3(n)\\[10pt]&\Leftrightarrow \beta\cdot n\cdot (\log_3(n))^2>2\cdot n\cdot \log_3(n)=n\cdot \log_3(n^2)\end{aligned}.$$
Also hat man damit \(n\cdot \log_3(n^2)\notin \Omega(n\cdot (\log_3(n))^2)\) gezeigt.
Insgesamt gilt also \(n\cdot \log_3(n^2)\notin \Theta(n\cdot (\log_3(n))^2)\).
