0 Daumen
406 Aufrufe



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...




von

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).

1 Antwort

0 Daumen

\(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).

von 88 k 🚀

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.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Antworten
Gefragt 16 Apr 2018 von Samz
1 Antwort
Gefragt 7 Mai 2021 von Gast
2 Antworten
Gefragt 17 Apr 2019 von Simon99
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community