Zeigen oder widerlegen Sie folgende Aussagen:

Question

Aufgabe:

\( \mathcal{O} \)-Notation Aussagen
Zeigen oder widerlegen Sie folgende Aussagen:
a) \( f(n) \in \mathcal{O}\left(f(n)^{2}\right) \)
b) \( \forall \varepsilon>0: n \log (n) \in \mathcal{O}\left(n^{1+\varepsilon}\right) \)
c) Wenn \( f(n) \in \mathcal{O}(g(n)) \), dann gilt \( 2^{f(n)} \in \mathcal{O}\left(2^{g(n)}\right) \)

Problem/Ansatz:

ich bekomme diese übungsaufgabe leider nicht hin, kann mir da jemand weiterhelfen? wie zeigt oder wiederlegt man so eine behauptung?

Answer 1

Ich benutzte die Definition

$$f\in \mathcal O(g) \Leftrightarrow \limsup_{n\to \infty}\left|\frac{f(n)}{g(n)}\right|< \infty$$

(a) - falsch

$$f(n) = \frac 1n \Rightarrow \frac{\frac 1n}{\frac 1{n^2}}= n \stackrel{n\to\infty}{\longrightarrow} \infty$$

(b) - richtig

$$\frac{n\log n}{n^{1+\varepsilon}} = \frac{\log n}{n^{\varepsilon}}\stackrel{\text{L'Hospital}}{\sim}\frac{\frac 1n}{\varepsilon n^{\varepsilon-1}}=\frac 1{\varepsilon n^{\varepsilon}}\stackrel{n\to\infty}{\longrightarrow} 0 <\infty$$

(c) - falsch

$$f(n) = 2n,\: g(n) = n \Rightarrow f\in \mathcal O(g)$$

$$\frac{2^{2n}}{2^n} = 2^n \stackrel{n\to\infty}{\longrightarrow} \infty$$

Comments

Vielen Dank, das hilft mir sehr weiter