0 Daumen
256 Aufrufe

Ich habe zwei Funktionen gegeben

$$ f(n)=2000n^2\\g(n)=2^n $$

Nun will ich zeigen, dass $$ f\notin \Omega(g) $$ gilt, bin mir aber nicht sicher, ob das so geht, wie ich es gemacht habe. Meine Idee war nun anzunehmen, dass es gilt, um es dann zu wiederlegen.

$$\text{Seien } f(n)=2000n^2, \quad g(n)=2^n \text{ gegeben.} \\\text{Angenommen es gelte }f\in \Omega(g).\text{ Dann gibt es ein }\beta>0 \text{ und ein } \\n_0\in\mathbb{N}\text{, sodass für alle }n\geq n_0\text{ die Abschätzung }\\f(n)\geq \beta\cdot g(n)\geq 0\text{ erfüllt ist. Wähle } \beta=2000 \text{ und }n_0=4.\text{ Dann ist}\\f(n)=2000n^2\geq 2000\cdot 2^n=2000\cdot g(n)\\\text{ein Widerspruch zur Aussage } \forall n\in\mathbb{N}_{\geq 4}:2^n>n^2.\\ \text{Damit folgt }f\notin \Omega(g). $$

von

1 Antwort

0 Daumen

Hallo hallo,

das geht leider so nicht ganz. Dir wird ja nur die Existenz mindestens eines \( \beta \) zugesichert, d.h. wenn du die Aussage widerlegen möchtest, musst du zeigen, dass kein solches \( \beta \) existiert. Du musst also zeigen, dass sich bei jeder möglichen Wahl von \( \beta \) ein Widerspruch ergibt, nicht nur für ein fest gewähltes.

Also: Angenommen \( f \in \Omega(g) \). Sei \( \beta > 0 \) beliebig, dann existiert ein \( n_0 \in \mathbb{N} \) mit

$$ f(n) \ge \beta \cdot g(n) \ge 0, \quad \forall n \ge n_0 $$

Da g(n) > 0 heißt das ja nichts anderes als

$$ \frac{f(n)}{g(n)} \ge \beta > 0 , \quad \forall n \ge n_0 $$.

Jetzt ist aber

$$ \lim\limits_{n\to\infty}  \frac{f(n)}{g(n)} = \lim\limits_{n\to\infty}  \frac{2000n^2}{2^n} \stackrel{\text{2x l'Hospital}}{=} \lim\limits_{n\to\infty}  \frac{4000}{\ln(2)^2 2^n} = 0 $$

Widerspruch.

Gruß

EmNero

von

Hallo, Danke für deine Antwort. Ich hatte vergessen zu erwähnen, dass diese Funktionen bei mir grundlegend als ℕ -> ℝ definiert waren. Statt L'H, muss ich dann einfach eine obere Abschätzung vornehmen?

Du kannst die Funktionen einfach von \( \mathbb{N} \to \mathbb{R} \) auf \( \mathbb{R} \to \mathbb{R} \) fortsetzen.

Wir zeigen durch die Konvergenz ja nur:

Sei \( 0 < \varepsilon < \beta \) (wähle zB \(\varepsilon := \frac{\beta}{2}\)) dann existiert ein \( x_0 \in \mathbb{R} \) s.d. für alle \( x≥x_0\) gilt

$$ \left|\frac{f(x)}{g(x)} -0 \right| < \varepsilon < \beta $$

Daraus kannst du aber auf jeden Fall folgern, dass ein \( n_0 \in \mathbb{N} \) existiert s.d. für alle \( n≥n_0\) gilt

$$ \left|\frac{f(n)}{g(n)}  \right| < \varepsilon < \beta $$

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community