0 Daumen
868 Aufrufe

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

Avatar von

1 Antwort

+2 Daumen
 
Beste Antwort

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

geht mit: c=7, n0=0

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

7c≥1 ⇔ c≥1/7

geht mit: c=1/7, n0=0

f(n) = n3+100n2 ≤ n3+100n3 =101n3≤ c*g(n) = cn3

geht mit c=101, n0=0

g(n) = n3 ≤ n3+100n2 ≤ c*f(n) = c*(n3+100n2)

geht mit c=1, n0=0

f(n) = 4n = 2n2n = 22n ≤ c*g(n) = c2^(2n)
geht mit c=1, n0=2 (also ab 3)

g(n) = 2^(2n) ≤ cf(n) = c4n = c22n

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

also ex kein n0 und kein c

Avatar von 4,3 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community