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\)