Beweis mit Landau-Symbolen

Question

Aufgabe:

Wahre Aussage Landau-Symbolik beweisen

Problem/Ansatz:

Ich habe folgende Aufgabe

O(f (n)) ∩ Ω(g(n)) ̸= ∅ ⇐⇒ g(n) ∈ O(f (n))

ich weiß, dass diese Aussage wahr ist und man nun mittels den Definitionen der Landau Symbole die Aussage allgemein beweisen muss. Ich weiß nur nicht wie ich den Beweis angehe und wie man das dann richtig notiert.

Ich wäre sehr dankbar, wenn mir jemand helfen könnte diese Aussage richtig zu beweisen.

Answer 1

Ich benutze folgende Vereinfachung der Schreibweise: \(f,g \geq 0\) (andernfalls musst du im Beweis unten überall \(|f(n)|,|g(n)|\) schreiben).

Außerdem benutze ich folgende Definitionen:

\(h\in O(f) \Leftrightarrow \exist n_0, C>0:\; h(n) \leq Cf(n)\) für \(n\geq n_0\)

\(h\in \Omega(g) \Leftrightarrow \exist n_1, c>0:\; h(n) \geq cg(n)\) für \(n\geq n_1\)

\(\Rightarrow\):
Für \(n\geq \max(n_0,n_1)\) haben wir

\(cg(n) \leq h(n)\leq Cf(n) \Rightarrow g(n) \leq \frac Cc f(n) \Rightarrow g\in O(f)\)

\(\Leftarrow\):

\(g\in \Omega(g)\) denn \(g(n) \geq 1\cdot g(n) \) für alle \(n\in \mathbb N\)

Da auch \(g\in O(f) \) folgt \(g \in O(f) \cap \Omega(g)\). Also

\(O(f) \cap \Omega(g) \neq \emptyset\)