O-Notation zwei Funktionen

Question

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}} \)

Answer 1

f(n) = 7n ≤ c*g(n) = cn

geht mit: c=7, n₀=0

g(n) = n ≤ c*f(n) = c*7n

7c≥1 ⇔ c≥1/7

geht mit: c=1/7, n₀=0

f(n) = n³+100n² ≤ n³+100n³ =101n³≤ c*g(n) = cn³

geht mit c=101, n₀=0

g(n) = n³ ≤ n³+100n² ≤ c*f(n) = c*(n³+100n²)

geht mit c=1, n₀=0

f(n) = 4ⁿ = 2ⁿ2ⁿ = 2²ⁿ ≤ c*g(n) = c2^(2ⁿ)
geht mit c=1, n₀=2 (also ab 3)

g(n) = 2^(2ⁿ) ≤ cf(n) = c4ⁿ = c2²ⁿ

dann müsste: c2²ⁿ ≥  2^(2ⁿ)  ⇔ c ≥  2^(2ⁿ)  / 2²ⁿ = 2^(2ⁿ-2n) → ∞, für n→ ∞,

also ex kein n₀ und kein c