Nutze
\( \lim \limits_{n \rightarrow \infty} \frac{f(n)}{g(n)}=0 \Longrightarrow g(n) \notin \mathcal{O}(f(n)) \)
Für das Erste also
\( \lim \limits_{n \rightarrow \infty} \frac{2^{n}}{2^{2 n}}=\lim \limits_{n \rightarrow \infty} 2^{n-2 n}=\lim \limits_{n \rightarrow \infty} 2^{-n}=0 \)
und somit
\( 2^{2 n} \notin \mathcal{O}\left(2^{n}\right) \)
Alternativ:
Nehme an, \( 2^{2 n} \in \mathcal{O}\left(2^{n}\right) \) und somit gilt für ein \( c \in \mathbb{R} \) und alle \( n \geq N \) für irgendein \( N \)
\( 2^{2 n} \leq c 2^{n} \Longleftrightarrow 2 n \leq \log _{2}(c)+n \Longleftrightarrow n \leq \log _{2}(c) \)
Das kann aber nicht sein, da \( n \) linear wächst und \( \log _{2}(c) \) eine Konstante ist. Ein Widerspruch.
