0 Daumen
315 Aufrufe

(∀g1, g2 : ℕ → ℕ)(∀ƒ1 ∈ Ο(g1))(∀ƒ2 ∈ O(g2)) :


1)

f1 + f2 ∈ O(g1 + g2)


2)

f1 * f2 ∈ O(g1 * g2)

von

Benutz die Definitionen von f ∈ O(g).

1 Antwort

0 Daumen
\(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\)

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...