0 Daumen
668 Aufrufe

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?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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.

Avatar von 4,6 k

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

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community