O-Notation Beweisen oder widerlegen

Question

Zu zeigen ist: \(f(n) = \Omega(g(n)) \Rightarrow 2^{f(n)} = \Omega(2^{g(n)})\)

Comments

Ich habe folgendes gemacht: Die Aussage ist wahr, wir wissen, dass wenn man 2 Zahlen gleicher Basis vergleicht, ist die Zahl mit der größeren Potenz größer. Aus \(f(n) = \Omega(g(n))\) folgt, dass \(f(n) \geq c_1 \cdot g(n)\) daher kann man schlußfolgern, dass \(2^{f(n)} \geq \Omega(2^{g(n)})\).

Richtig oder nicht ?

---

EDIT: Dein Kommentar unten wird nicht richtig umgewandelt.

Answer 1

$$n/2=\Omega(n)\Rightarrow 2^{n/2}=\sqrt{2}^{\,n}=\Omega(2^n)$$

Comments

Irgedwie verstehe ich diesen Beweis/Gegenbeispiel gar nicht.  Du sagst ,dass

\(f(n) = \frac{n}{2}  = \Omega(n)\) aber das ist doch falsch  \(\frac{n}{2}\) ist doch kleiner aus n.

Also was ist f(n) und was ist g(n) in dem Beispiel ?

---

Wenn Du meinst, dass \(n/2=\Omega(n)\) falsch ist, dann solltest Du Dir st die Definition der \(\Omega\)-Notation anschauen.

---

\(f(n) = \Omega(g(n))\) bedeutet \(\exists k > 0, \forall n, \exists n > n_0 : f(n) \geq k * g(n)\).

D.h. f(n) soll mindestens so groß, wie g(n) wachsen also f(n) soll größer sein, aber \(\frac{n}{2} < n\).

---

Deine Quantoren sind verrutscht. Jedenfalls wird bloss \(k>0\) verlangt. Da ist z.B. \(k=1/2\), was bzgl. \(n/2=\Omega(n)\) zur wahren Aussage \(n/2\ge 1/2\cdot n\) fuehrt, erlaubt.

---

Achso ich glaube, dass ich schon verstanden habe, also dein Gegenbeispiel richtig aufgeschrieben wäre dann:

Wir wissen, dass folgendes gilt:

\(\exists k > 0, \forall n, \exists n > n_0 : f(n) \geq k * g(n)\)

Sei \(f(n) = \frac{n}{2}, g(n) = n\), das gilt, denn wir wählen \(k=\frac{1}{2} \Rightarrow \frac{n}{2} \geq \frac{1}{2} * n\) , dann ist aber \(2^{f(n)} = 2^{\frac{n}{2}} = \sqrt{2}^n \not= \Omega(2^n) = \Omega(2^{g(n)})  \)

---

Mein Gegenbeispiel ist schon so richtig aufgeschrieben. Hingegen sind Deine Quantoren immer noch ein ungeniessbares Durcheinander. Man darf annehmen, dass Du es selber nicht verstehst. Deshalb eine Formulierung in Worten: \(f(n)=\Omega(f(n))\) bedeutet, dass es eine Konstante \(K>0\) gibt, sodass \(f(n)\ge Kg(n)\) für fast alle \(n\) gilt.

---

Ne ich verstehe es, aber ich habe es einfach von oben kopiert und nicht drauf aufegepasst, aber ich weiß schon, wie das geht. Aber trotzdem um das Beispiel richtig aufzuschreiben muss man so bisschen mehr Sachen sagen. Zum Beispiel: Die Aussage ist falsch, denn Sei f(n) = n/2 und g(n), dann ist \(2^{f(n)} = 2^{n/2] = \sqrt{2}^n \not = \Omega(2^n) = \Omega(2^{g(n)}.\)