Aufgabe:
Für zwei Funktionen \( f, g: \mathbb{N} \rightarrow \mathbb{N} \) schreiben wir \( f \in o(g), \) falls für alle Konstanten \( c \in \mathbb{R}^{+} \) \( \operatorname{ein} n_{0} \in \mathbb{N} \) gibt so, dass für alle \( n>n_{0} \) gilt, \( f(n) \leq c \cdot g(n) \)
a) Sei \( f(n)=1000 \cdot n \) und \( g(n)=n^{2} . \) Zeigen Sie \( f \in o(g) \).
b) Sei \( f(n)=256 \) und \( g(n)=2 n . \) Zeigen Sie \( f \in o(g) \).
c) Sei \( f(n)=2^{n} \) und \( g(n)=2^{2 n} . \) Zeigen Sie \( f \in o(g) \).
d) Sei \( f(n)=1000 \cdot \min \left\{k \geq 1 | k^{2} \geq n\right\} \) und sei \( g(n)=n-9000 . \) Zeigen Sie \( g \notin o(f) \).
Problem/Ansatz:
Für Ansätze sowie Lösungen zur Kontrolle wäre ich sehr dankbar :)
