0 Daumen
319 Aufrufe

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.

Avatar von

1 Antwort

0 Daumen

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

Avatar von 11 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
0 Antworten
0 Daumen
0 Antworten

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community