Ich interpretiere die gegebenen Zeichenfolgen mal wie folgt als Fragen:
1.) Gilt \(n^2\in O(2^n)\) ?
Ja, für alle \(n\geq 4\) gilt schließlich \(n^2\leq 2^n\)
2.) Gilt \(2^n\in O(n^2)\) ?
Nein. Die Funktion \(\frac{2^n}{n^2}\) ist streng monoton steigend für \(n>5\) und nach oben hin unbeschränkt (\(\lim_{n\to \infty} \frac{2^n}{n^2} = \infty\)), daher finden wir für jedes \(c\in \mathbb{R}^+\) und \(n_0\in \mathbb{N}^+\) ein \(n\geq n_0\) mit \(\frac{2^n}{n^2}>c \Rightarrow 2^n > c\cdot n^2\).
3.) Gilt \(O(1) \subseteq O(10^{28928398})\) ?
Ja. Wählen wir eine beliebige Funktion \(f\in O(1)\).
Dann gibt es ein \(c\in \mathbb{R}^+\) und \(n_0 \in \mathbb{N}^+\) mit \(f(n)\leq c \cdot 1 = c\) für alle \(n\geq n_0\).
Wählen wir \(c'=c\), so folgt offenbar \(f(n)\leq c = c' \leq c'\cdot 10^{28928398}\).
Damit folgt \(f\in O(10^{28928398})\).
4.) Gilt \(O(10^{28928398}) \subseteq O(1)\) ?
Ja. Wählen wir eine beliebige Funktion \(f\in O(10^{28928398})\).
Dann gibt es ein \(c\in \mathbb{R}^+\) und \(n_0 \in \mathbb{N}^+\) mit \(f(n)\leq c \cdot 10^{28928398}\) für alle \(n\geq n_0\).
Wählen wir \(c'=c\cdot 10^{28928398}\), so folgt offenbar \(f(n)\leq c\cdot 10^{28928398} = c' \leq c' \cdot 1\).
Damit folgt \(f\in O(1)\).
5.) Gilt \(O(n^2)\subseteq O(0)\) ?
Nein. Wählen wir zum Widerlegen die Funktion \(n^2\in O(n^2)\) und zeigen \(n^2\notin O(0)\).
Für beliebig gewählte \(c\in \mathbb{R}^+\) und \(n_0\in \mathbb{N}^+\) finden wir nämlich ein \(n=max\{n_0, 1\}\geq n_0\) mit
\(n^2\geq 1>0=c\cdot 0\).
6.) Gilt \(O(0)\subseteq O(n^2)\) ?
Ja. Wählen wir eine beliebige Funktion \(f\in O(0)\).
Dann existiert ein \(n_0 \in \mathbb{N}^+\) mit \(f(n)\leq 0\) für alle \(n\geq n_0\), offensichtlich wg. \(0\leq n^2\) also auch \(f(n)\leq n^2\), damit folgt \(O(0)\subseteq O(n^2)\).
