Beweis O-Notation mit Addition

Question

Aufgabe: Wir haben ein Skript bekommen zu O-Notationen und asymptotischen

Text erkannt:

2) Summen und Produkte

Für alle \( f_{1}, f_{2}, g_{1}, g_{2}: \mathbb{N} \longrightarrow \mathbb{R}^{+} \)folgt gilt:
\( \left[f_{1}(n) \in \mathcal{O}\left(g_{1}(n)\right) \wedge f_{1}(n) \in \mathcal{O}\left(g_{1}(n)\right)\right] \Longrightarrow f_{1}(n)+f_{2}(n) \in \mathcal{O}\left(g_{1}(n)+g_{2}(n)\right) \)

Begründung mit dem Quotientenkriterium:
\( \frac{f_{1}(n)+f_{2}(n)}{g_{1}(n)+g_{2}(n)}=\frac{f_{1}(n)}{g_{1}(n)+g_{2}(n)}+\frac{f_{2}(n)}{g_{1}(n)+g_{2}(n)} \leq \frac{f_{1}(n)}{g_{1}(n)}+\frac{f_{2}(n)}{g_{2}(n)} \leq K_{1}+K_{2} \)

Analoge Regeln gelten für die Multiplikation an Stelle der Addition und für \( \Omega, o \) bzw. \( \omega \) an Stelle \( \operatorname{von} \mathcal{O} \)

Laufzeiten. Jedoch verstehe ich den ein Beweis nicht.

Problem/Ansatz: Ich bin verwirrt wie man mit dem Quotientenkriterium diese Abschätzung wählt.

Answer 1

Wird wohl so sein:

\( \left[f_{1}(n) \in \mathcal{O}\left(g_{1}(n)\right) \wedge f_{2}(n) \in \mathcal{O}\left(g_{2}(n)\right)\right] \)

 \(\Longrightarrow f_{1}(n)+f_{2}(n) \in \mathcal{O}\left(g_{1}(n)+g_{2}(n)\right) \)

Also gibt es ein K1 mit \(  \frac{f_{1}(n)}{g_{1}(n)} \leq K_{1} \) und \(  \frac{f_{2}(n)}{g_{2}(n)} \leq K_{2} \)

Dann wird doch sicher die Abschätzung klar.

Comments

Ah ja stimmt, das macht Sinn, danke. Und bei Es seien Funktionen f(x) = o(x) und g(x) = o(x) für x → 0 gegeben. Zeigen oder widerlegen Sie:
f (x) + g(x) = o(x). Wäre es dann die gleiche Herangehensweise, also f(x) + g(x) / 2o(x) = f(x) / 2o(x) + g(x) / 2o(x) <= (f(x) / o(x)) + ( g(x) + o(x))