Formaler Beweis O-Notation

Question

Aufgabe:

Formaler Beweis, dass für gegebenes g : ℕ → ℝ^>0 die Notationen gleich sind.

Problem/Ansatz:

Leider fehlt mir die Kreativität, dieses Problem zu lösen.

Ich hab schon daran gedacht, das n₀ und den dazugehörigen Existenzquantor zu streichen. Mir ist leider nicht ganz klar ob ich einfach etwas aus einer Gleichung streichen kann, obwohl dies eine Implikation beinhaltet.

Answer 1

Aloha :)

Willkommen in der Mathelounge... \o/

In beiden Definitionen \(D_1\) und \(D_2\) gibt es eine Konstante \(c\), sodass \(f(n)\le c\cdot g(n)\) ist. Diese Konstante muss aber nicht in beiden Fällen dieselbe sein.

Bei der ersten Definition \(D_1\) muss diese Ungleichung nur für fast alle \(n\) gelten.

Bei der zweiten Definition \(D_2\) muss diese Ungleichung für alle \(n\) gelten.

1. Fall \(D_2\implies D_1\)

Diese Richtung ist sofort klar, denn wenn \(f(n)\le c \cdot g(n)\) für alle \(n\in\mathbb N\) ist, gilt auch \(D_1\) mit \(n_0=1\).

2. Fall \(D_1\implies D_2\)

Wir wissen, dass für alle \(n\ge n_0\) die Bedingung \(f(n)\le c\cdot g(n)\) erfüllt ist.

Für alle \(n<n_0\) bilden wir die Menge \(M\coloneqq\left\{\frac{f(1)}{g(1)},\frac{f(2)}{g(2)},\cdots,\frac{f(n_0-1)}{g(n_0-1)}\right\}\) und setzen: \(\tilde c\coloneqq\operatorname{max}\left\{M,c\right\}\).

Dann gilt \(f(n)\le\tilde c\cdot g(n)\) für alle \(n\in\mathbb N\).

Comments

Vielen Dank!:)

---

Könntest du nochmal erklären, was genau die Menge M und das ć:=max{M, c} machen?

VG

---

Wir wissen, dass für alle \(n\ge n_0\) bereits gilt:$$f(n)\le c\cdot g(n)\quad\text{bzw.}\quad\frac{f(n)}{g(n)}\le c$$Für alle \(n<n_0\) bestimmen wir alle Quotienten und sammeln sie in einer Menge

$$M=\left\{\frac{f(1)}{g(1)}\,,\,\frac{f(2)}{g(2)}\,,\,\frac{f(3)}{g(3)}\,,\,\frac{f(4)}{g(4)}\,,\cdots,\,\frac{f(n_0-1)}{g(n_0-1)}\right\}$$

Wählen wir von diesen den größten Quotienten und nennen ihn \(c_1\), so gilt:$$\frac{f(n)}{g(n)}\le c_1\quad\text{für alle }n<n_0$$

Wenn wir jetzt von \(c_1\) und von \(c\) noch den größten auswählen und ihn \(\tilde c\) nennen, dann gilt:$$\frac{f(n)}{g(n)}\le\tilde c\quad\text{für alle }n\in\mathbb N$$

---

Top, vielen Dank!:)