O kalkül zeigen oder widerlegen

Question

Aufgabe:

• O(g(n))={ f(n) | ∃ c>0 ∃ n0>0 ∀ n≥n0: f(n) ≤ c⋅g(n) }
• Ω(g(n))={ f(n) | ∃ c>0 ∃ n0>0 ∀ n≥n0: f(n) ≥ c⋅g(n) }
• Θ(g(n)) = O(g(n)) ∩ Ω(g(n))
• o(g(n))={ f(n) | ∀ c>0 ∃ n0>0 ∀ n≥n0: f(n) ≤ c⋅g(n) }
• ω(g(n))={ f(n) | ∀ c>0 ∃ n0>0 ∀ n≥n0: f(n) ≥ c⋅g(n) }

Zeigen Sie die folgenden beiden Aussagen elementar (d.h. nur mit Hilfe der Denitionen der O-, Ωund Θ-Kalküle) oder widerlegen Sie mithilfe eines Beispiels:
Für beliebige positive Funktionen f : N → N und g : N → N gilt

Aus f(n) = O(g(n)) folgt, dass 2^(f(n)) = O(2^(g(n))) )

Problem/Ansatz:

∃ c1>0 ∃ n1>0 ∀ n>n1: f(n) ≤ c1⋅g(n) 

Daraus folgt: no=max{n1} ∃no>0  ∀n>no

2^(f(n))<=2^(c1*g(n))<=(2^c1)^g(n)  weiter komme ich nicht, weder kann ich es weiterumformen noch ein Gegenbeispiel finden. Ich bitte um Hilfe, danke :)

Comments

Für Leute, die die Struktur des Beitrags nicht durckblicken:

Am Anfang stehen die Definitionen der einzelnen Klassen. Danke an OP dafür. Dadurch kann man die Aufgabe auch ohne Spezialwissen lösen.

Danach folgt die Aufgabenstellung. Lasst euch nicht davon verwirren, dass dort von den "folgenden beiden Aussagen" die Rede ist, aber nur eine Aussage folgt. Vermutlich hat OP mit der zweiten Aussage keine Probleme oder möchte diese vielleicht selbst lösen.

Der Missbrauch der Notation ist so üblich, dass sogar Dozenten darauf hinweisen: mit "f(n) = O(g(n))" ist "f(n) ∈ O(g(n))" gemeint.

Im Abschnitt Problem/Ansatz folgt noch mal die für die Aufgabenstellung relevante Definition. Die Ungleichung 2^(f(n))<=2^(c1*g(n)) muss für ein c1 und alle n≥n1 gezeigt werden. 2^(c1*g(n)) wurde mit Potenzgessetzen umgeformt zu (2^c1)^g(n). Das ist der übliche Weg, wenn man davon ausgeht, dass die Aussage wahr ist.

Alles in Allem sehe ich keinen Grund dafür, den Beitrag als Spam zu markieren. Lediglich aus "no=max{n1} ∃no>0  ∀n>no" werde ich nicht schlau.

---

Ich finde man sollte solche Texte entweder mit einem Computerprogramm schreiben oder original als Foto hochladen.

---

Bevor man so etwas von einem FS fordert, sollten gewisse Helfer erst einmal selbst damit anfangen! Für mich ist der Beitrag auch vollkommen klar.

---

Alles in Allem sehe ich keinen Grund dafür, den Beitrag als Spam zu markieren.

Das haben bestimmt Leute gemacht, die mit der Aufgabe überfordert waren.

Danke für deine Erläuterungen, oswald!

Answer 1

Gegenbeispiel: \(f: n\mapsto 2n,\ g: n\mapsto n\)