O-Notation: Beweisen oder widerlegen sie die folgenden Aussagen

Question

Gegeben sind zwei Funktionen f1, f2 : ℕ → ℝ⁺ , für die gilt f1 ∈ O(g) und f2 ∈ O(g).

f1 + f2 ∈ O(g)

f1(n), f2(n) = log n

log(n) + log(n) = O(log(n)), daher ist die Aussage richtig? Kann ich das so beweisen?

Answer 1

Gegeben sind zwei Zahlen a, b ∈ ℝ , für die gilt a < 5 und b < 5.

a + b < 5

a, b = 2

a + b = 4, daher ist die Aussage richtig!

Überleg mal, ob du diese Aussage auch so beweisen kannst.

Comments

Aha dann müsste ich eigentlich nur sagen O(g) ist auch log n, kleiner muss es ja nicht sein, reicht auch gleich oder?

f1(n), f2(n), O(g) = log n

log(n) + log(n) = O(log(n)), daher ist die Aussage richtig?

Oder muss ich das mit der groß O Definition zeigen?

---

Oder muss ich das mit der groß O Definition zeigen?

Nein, musst du nicht. Du darfst auch jeden Satz über Landau-Symbole verwenden, den ihr bewiesen habt. Falls es da noch nichts gibt, dann ist aber tatsächlich der Rückgriff auf die Definition die einzige Möglichkeit.

Insbesondere wollte ich aber mit meinem Beitrag verdeutlichen, dass man eine allgemeine Aussage nicht beweisen kann, indem man sich ein paar Beispiele herausgreift (f₁(n) = log n und f₂(n) = log n in deinem Fall). Man kann doch auch nicht sagen, das jede Zahl durch drei teilbar ist, weil zum Beispiel 18 und 54 druch 3 teilbar sind.

---

Welche Sätze meinst du da? Ich hab die Definitionen von O,Θ und Ω, die Regeln für Kalküle zb Transitivität aber wie ich das jetzt einsetze ka mit dem Zeugs häng ich schon voll lang... Ja stimmt war blöd von mir das einfach anzunehmen!