O-Notation Beweisaufgaben

Question

Aufgabe:  zu zeigen oder widerlegen ist: f1 = O(g1), f2 = O(g2) ⇒ f1 + f2 = O(g1 + g2) für f, f1, f2, g, g1, g2 : N → R≥0

Problem/Ansatz: Mein Ansatz wäre mit dem Quotientenkriterium zu argumentieren allerdings bin ich mir nicht sicher wie ich dies konkret aufschreiben würde.

Answer 1

f1 = O(g1)

Seien N₁ ∈ ℕ, c₁ > 0, so dass

        |f₁(x)| < c₁·g₁(x)     ∀x > N₁

ist.

f2 = O(g2)

Seien N₂ ∈ ℕ, c₂ > 0, so dass

        |f₂(x)| < c₂·g₂(x)     ∀x > N₂

ist.

Dann ist

            |(f₁+f₂)(x)|
        < |f₁(x)| + |f₂(x)|
        < c₁·g₁(x) + c₂·g₂(x)
        ≤ c·(g₁+g₂)(x)        ∀x > max(N₁, N₂)

mit c = max(c₁, c₂).