Beweisen Sie: o(g(n)) ⊄ O(g(n)).

Question

Aufgabe:

Beweisen Sie:

Sei g: ℕ→ℝ, dann gilt o(g(n)) ⊄ O(g(n)).

Problem/Ansatz:

Können Sie mir bitte ein Paar Tipps, wie ich genau vorgehen kann?

Comments

Das Teilmengensymbol ist falsch. Wir besuchen dieselbe Veranstaltung und in der Aufgabe ist von der "echten Teilmenge" die Rede. Das Zeichen, was du da benutzt ist "keine echte Teilmenge"

https://de.wikipedia.org/wiki/Teilmenge

Answer 1

Ich nehme an, dass eigentlich \(o(g)\subsetneq O(g)\) gemeint ist:

Man hat \(g\in O(g)\), aber \(g\notin o(g)\).

Comments

Und soll ich jetzt diese Bedingung beweisen?

---

Klar ;-) \(\;\;\;\;\)

---

wie denn genau

---

welche Versuche hast du denn unternommen, um

die Aussagen zu verifizieren?

---

Für o(g(n)) hat man alle c > 0, für die ein n₀  existiert, sodass I f(n) I < c I g(n) I für alle n > n₀ 

Und für O(g(n)) existiert nur ein c > 0 und n₀ sodass I f(n) I < c I g(n) I für alle n > n0

Man nimmt eine Funktion f mit f∈O(g(n)), für die aber nicht f∈o(g(n)) gilt, die Funktion f f=g selbst