Aufgabe:
Zur Erinnerung: Für zwei Funktionen \( f, g: \mathbb{N} \rightarrow \mathbb{N} \) schreiben wir \( f \in O(g), \) wenn es \( c \in \mathbb{R}^{+} \) und \( n_{0} \in \mathbb{N} \) gibt so dass für alle \( n>n_{0} \) gilt, dass \( f(n) \leq c \cdot g(n) \)
a) Geben Sie für die folgenden Paare von Funktionen jeweils an, ob \( f \in O(g) \) oder ob \( g \in O(f) . \) Begründen Sie Ihre Aussage jeweils wie folgt: Um zu zeigen, dass \( f \in O(g) \) geben Sie ein \( c \in \mathbb{R}^{+} \) und ein \( n_{0} \in \mathbb{N} \) an, so dass \( f(n) \leq c \cdot g(n) \) für alle \( n>n_{0} . \) Das Kriterium gilt analog für \( g \in O(f) \)
i) \( f(n)=7 n \) und \( g(n)=n \)
ii) \( f(n)=n^{3}+100 n^{2} \) und \( g(n)=n^{3} \)
iii) \( f(n)=4^{n} \) und \( g(n)=2^{2^{n}} \)