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 \in \mathbb{N} \ \forall 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 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 3n^3+200 \leq \alpha \cdot \left( \frac{1}{2}n^3-10 \right)\).
Um jetzt an diese beiden Werte ranzukommen, kannst du das (gerade bei Polynomen) schön sukzessive nach unten abschätzen. Dabei kann man sich den Leitkoeffizienten des Polynoms anschauen und würde hier schonmal sehen, dass \(\alpha=7>0\) ein geeigneter Kandidat sein könnte. Also kann man jetzt mal probieren:
\(\alpha\cdot g(n)=7\cdot g(n)=7\cdot \left(\frac{1}{2}n^3-10\right)\\=\frac{7}{2}n^3-70\\=\frac{6}{2}n^3+\frac{1}{2}n^3-70\\=3n^3+\frac{1}{2}n^3-70\\=3n^3+200+\left(\frac{1}{2}n^3-270\right )\\\stackrel{n\geq 10}{\geq} 3n^3+200+230\geq 3n^3+200\geq 0\).
Die Wahl \(n=10\) kann man dadurch rechtfertigen, dass die Ungleichung
\(\frac{1}{2}n^3-270\geq 230\) für alle \(n\in \mathbb{N}_{\geq 10}\) erfüllt ist.
Insgesamt gilt also mit \(\alpha=3\) und für alle \(n\geq 8=:n_0\) die Ungleichung
\(0\leq 3n^3+200 \leq \alpha \cdot \left( \frac{1}{2}n^3-10 \right)\).
Zu (b) Hier gilt doch schonmal \(\sqrt{n}\leq 4^{\sqrt{n}}\). Wenn du davon noch nicht überzeugt bist, beweise es. Versuche dann damit weiterzuarbeiten.
Zu (c). Kannst du analog wie (a) durchführen.
