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!:)