Beweisen Sie die folgenden angegebenen Rechenregeln.

Question

(∀g₁, g₂ : ℕ → ℕ)(∀ƒ₁ ∈ Ο(g₁))(∀ƒ₂ ∈ O(g₂)) :

1)

f₁ + f₂ ∈ O(g1 + g2)

2)

f₁ * f₂ ∈ O(g1 * g2)

Comments

Benutz die Definitionen von f ∈ O(g).

Answer 1

\(f_1 + f_2 \in \mathcal{O}(g_1 + g_2)\)

Seien \(f_1(n)\leq c_1\cdot g_1(n)\) und \(f_2(n)\leq c_2\cdot g_2(n)\) für \(c_1,c_2\in\mathbb{R}_0^+\) und alle \(n\geq n_1\) bzw. alle \(n\geq n_2\). Dann gilt: 

\(f_1(n)+f_2(n)\leq c_1\cdot g_1(n)+c_2\cdot g_2(n)\leq c(g_1(n)+g_2(n))\) 

mit \(c=\max(c_1,c_2)\). \(\square\)

\(f_1 \cdot f_2 \in \mathcal{O}(g_1 \cdot g_2)\) 

Es gilt: 

- \(f_1(n)\in\mathcal{O}(g_1(n))\Longrightarrow\exists c_1,n_1\) mit \(f_1(n)\leq c_1\cdot g_1(n)\) für alle \(n\geq n_1\)

- \(f_2(n)\in\mathcal{O}(g_2(n))\Longrightarrow\exists c_2,n_2\) mit \(f_2(n)\leq c_2\cdot g_2(n)\) für alle \(n\geq n_2\)

Sei \(n_0=\max(n_1,n_2)\). Dann gelten diese beiden Ungleichungen auch für jedes \(n\geq n_0\). Das Multiplizieren dieser beiden Ungleichungen liefert

\(f_1(n)\cdot f_2(n)\leq c_1\cdot c_2\cdot g_1(n)\cdot g_2(n)\) für alle \(n\geq n_0\)

Daraus folgt: \(f_1(n)\cdot f_2(n)\in\mathcal{O}(g_1(n)\cdot g_2(n))\) \(\square\)