Beweis O-Notation. f und g streng monoton…

Question

ich soll folgende Aussage zeigen oder widerlegen:

Seien f: ℕ->ℕ, g:ℕ ->ℕ beliebig streng monton steigende Abbildungen.

Zeigen oder widerlegen sie: Ist f ∉ O(g) => g ∈ O(f).

Ich würde der Aussage zustimmen, aber wüsste nicht, wie ich es "formal" richtig aufschreibe...

Comments

Ich würde der Aussage zustimmen, aber wüsste nicht, wie ich es "formal" richtig aufschreibe...

Dann gib Deine Argumente doch informal wieder. Weitaus besser als gar nichts und schon mehr als die halbe Miete (wenn sie stimmig sind).

Answer 1

\(f(n) := \begin{cases}1&\text{falls }n=0\\\max(f(n-1), g(n-1))\cdot n&\text{falls $n$ ungerade}\\\max(f(n-1), g(n-1))\cdot n^2&\text{falls }n\neq 0\text{ und $n$ gerade}\end{cases}\)

\(g(n) := \begin{cases}1&\text{falls }n=0\\\max(f(n-1), g(n-1))\cdot n^2&\text{falls $n$ ungerade}\\\max(f(n-1), g(n-1))\cdot n&\text{falls }n\neq 0\text{ und $n$ gerade}\end{cases}\)

Die Abbildungen sind streng monoton und es gilt weder g∈O(f), noch f∈O(g).

Comments

Aber f(0) = 1 ist in O(1), genau wie g(0) = 1. Oder irre mich?

---

Aber f(0) = 1 ist in O(1)

f(0) ist eine Zahl.

O(1) ist eine Menge von Funktionen.

Die Fage, ob eine Zahl Element einer Menge von Funktionen sei, ist mit einem klaren Nein zu beantworten.