Zeige oder widelege folgende O-Notation Aussagen

Question

Aufgabe:

Zeigen oder widerlegen Sie folgende Aussagen:

Text erkannt:

a) \( f(n)=\mathcal{O}\left(f(n)^{2}\right) \)
b) \( \forall \epsilon>0: n \log (n)=\mathcal{O}\left(n^{1+\epsilon}\right) \)
c) Wenn \( f(n)=\mathcal{O}(g(n)) \), dann gilt \( 2^{f(n)}=\mathcal{O}\left(2^{g(n)}\right) \)

Answer 1

Hallo :-)

Gucke dir doch bitte die Definition an:

$$\mathcal{O}(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ \underbrace{0\leq f(n) \leq \alpha \cdot g(n)}_{0\leq f(n) \ \land f(n)\leq \alpha\cdot g(n) }  \} $$

und arbeite damit.

Zu a). Falsch. Betrachte zb \(f(n)=\frac{1}{n}\).

Zu b). Falsch.

Zu c). Richtig.