Implikation zu beweisen (O-Kalkül)

Question

Hallo liebe user,

ich in gerade dabei mit dem O-Kalkül zu rechnen. Das normale Berechnen des O-Kalküls ist für mir jetzt kein Problem, bin jedoch bei folgendem Problem stark gegen die Wand gefahren.

∀ f, g : ℕ → ℕ: f(n) ∈ Ο (g(n)) ⇒ 2^f(n) ∈ Ο (2^g(n))
Hierbei soll ich die Implikation beweisen. 
Ich sehe die Korrecktheit dieser Aussage auch.

Jedoch weiß ich nicht wie ich den Beweis angehen soll.

Ob mir da eine helfen könnte.
,
mit freundlichen Grüße
Snelfie

Answer 1

Also ich kann dir sagen, wie ich an diese Aufgabe rangegangen bin. Ich bin dabei über die Definition der O-Notation gegangen. also f(n) ∈ Ο (g(n)) <=>

Es gibt ein c und ein n₀ sodass für alle n>n₀ gilt 0 ≤ f(n) ≤c * g(n).

Da dies gilt, kann man eben jenes c nehmen und sagen, dass 2^f(n)  ≤  2^c*g(n)  für alle n ≥n_0. Nach Definition gilt also 2^f(n) ∈ Ο (2^g(n)).

Oh und da f(n) ≥ 0 ist 2^f(n) ≥ 0. 

Comments

Also ich hab mir noch folgendes überlegt

wenn f(n) = 2n und g(n) = n für alle natürlichen zahlen n,
somit gilt: f(n) ≤ 2g(n) für alle natürlichen zahlen n,

also: f(n) = O(g(n))

Angenommen  folgendes gilt: 2^f(n) ∈ Ο (2^g(n)),

dann existiert eine natürliche zahl n₀ und eine Konstante c > 0 so dass: 

4ⁿ = 2²ⁿ = 2^f(n) ≤ c2^g(n) = c2ⁿ

z.B: 2ⁿ = (4/2)ⁿ ≤ c, für alle n > n₀ was jedoch unmöglich ist.

Ist das richtig? Und wenn ja, hab ich damit dann die Implikation wiederlegt?

---

Wie du drauf kommst, das (4/2)^n ≤ c weiss ich nicht, denn das sieht falsch aus.

Was ich vergesseb hab zu sagen ist, dass man im letzten schritt noch beweisen muss, dass man 2^{c*cg (n)} zu etwas wie c' * 2^g (n) umformen kann.

Notfalls kann man auch die Regel für Grenzwerte benutzen die sagt: f (n) ∈ O (g (n)) <=>

0 ≤ Lim sup (f (n)/g(n)) = c < ∞

Zweiteres ist einfacher

---

und du bist dir sicher dass diese Implikation echt richtig ist? Denn ich habe jetzt schon verschiedene Lösungen gefunden. Jedoch besagen die eine Lösungen dass die Implikation richtig ist und die anderen Lösungen besagen dass die Implikation falsch ist. Dies leider mit ganz unterschiedlichen Begründungen, die aber immer logisch erscheinen. Weiß jetzt nicht auf welche Lösung ich mich jetzt verlassen kann.

---

Ja hab jetzt auch wieder Probleme mit meinen Beweisen. Ich kann dir heute abend weiteres berichten. Solange f (n) nicht in Θ (g (n)) ist, funktioniert es auf jeden fall. Im Grenzfall muss ich nochmal schauen

---

hier ist das was ich noch gefunden habe. Schau da mal rein:

http://stackoverflow.com/questions/23492509/big-o-notation-algebra/23493414#23493414
http://stackoverflow.com/questions/33220807/big-o-as-an-exponent-on-both-sides/33224992#33224992
http://wwwmayr.in.tum.de/lehre/2007WS/fa-cse/tutorials/tutorial03-solutions.pdf (problem 2)
http://www.math.lsa.umich.edu/~lspice/class/416/F2005/tex/2005Math416Homework2Solutions.pdf (erste seite beispiel d))

---

So. Ich muss mich korrigieren. Dir Implikation gilt definitiv nicht immer. Man kann z.B. als f (n) = x^2 + 5x und g (n) = x^2 definieren.

Dann gilt f (n) ∈ O (g (n))

2^{f (n)} ∈ O (2^{g (n)}) gilt nicht, da lim sup (2^{f (n)}/2^{g (n)}) = ∞.