Landau Symbole O-Notation

Question

Zeige oder widerlege:

a) $2^{2 n}=O\left(2^{n}\right)$

b) $\log _{a}(n)=O\left(\log _{b}(n)\right)$

c) $\log _{b}(n)=O\left(\log _{a}(n)\right)$

Kann mir da bitte jemand helfen?

Answer 1

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.

Comments

Danke danke. Fällt dir zu b) und c) auch noch was ein

---

Die stimmen beide, schau dir mal die Logarithmus Gesetze an, du kannst beide als einen Logarithmus der Basis e schreiben.

---

Ich danke dir

---

Gerne die Antwort akzeptieren, wenn sie hilfreich war :D