$$\text{Landau-Symbole } f \notin \Omega(g) $$

Question

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). $$

Answer 1

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

Comments

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 $$