O-Notation: Ungleichungen mit Induktion zeigen

Question

Aufgabe:

Beweisen Sie die folgenden Ungleichungen. Zu einem korrekten Beweis gehört die Angabe einer Konstante c > 0 und eines N ∈ ℕ, sodass für alle n ≥ N gilt: f(n) ≤ c · g(n).

Hinweis: Benutzen Sie die Definition der O-Notation und vollständige Induktion.

a) O(2ⁿ) < O(n!)

b) O(log(n)) < O(\( \sqrt{n} \))

c) O(n · log(n)) < O(n²)

Problem/Ansatz:

Wie findet man die passende Konstante? Wurde halt so gar nicht erklärt wie man drauf kommen soll und voll. Induktion sollte dann ansich funktionieren. Wäre nett, wenn es bei a) oder (vorallem) b) gezeigt werden könnte.

Comments

Wie kommst gerade auf 1? Weil in einem Beispiel wie in c) hat der Übungsleiter log_ab bestimmt, deshalb bin ich verwirrt, wie man das konkret bestimment soll.

Answer 1

Als passende Konstante kannst du 1 verwenden.

Das N bekommst du indem du dir die Graphen von einem Computer zeichnen lässt.

Jetzt fehlt nur noch die Induktion.

Comments

Wie kommst du gerade auf 1? Denn in dem einzigen Beispiel, dass gezeigt wurde (fast identisch mit c), nur das nicht O(n²), nur O(n) verwendet wurde. Da wurde dann aufwendig für die Konstante log_a(b) gewählt.

---

c), nur das nicht O(n²), nur O(n) verwendet wurde.

Dass kann nicht sein. Die Behauptung

        O(n·log n) ≤ O(n)

ist falsch.

Da wurde dann aufwendig für die Konstante log_a(b) gewählt.

Bist du sicher, dass das c war und nicht N?

Wie kommst gerade auf 1

Ich habe mir die Graphen der Funktionen angeschaut.

O(2ⁿ) < O(n!)

Links wird beim Übergang von n zu n+1 mit 2 multipliziert.

Rechts wird beim Übergang von n zu n+1 mit n+1 multipliziert.

Es ist intuitiv klar, das es rechts schneller wächst, da ändert auch ein konstanter Faktor c nichts dran. Also nehme ich den einfachsten legalen Faktor.

O(log(n)) < O(\( \sqrt{n} \))

Die Exponentialfunktion wächst schneller als jede Potenzfunktion.

Umgekährt wächst dann natürlich die Umkehrfunktion der Exponentialfunktion langsamer als die Umkehrfunktion jeder Potenzfunktion.

Ein Beispiel wo c = 1 nicht reicht, ist

O(n + sin(n)) ≤ O(n),

aber so abstrus sehen deine Aufgaben ja nicht aus.

---

Ich hab jetzt nochmal genauer geschaut, was der Leiter gemacht hat:

Sein Beispiel ist: O(log n) ≤ O(n)

log_ab ≡ const.

Basis des Log. ist unerheblich.

Dann wählt er O(log₂n) ≤ O(n)

Und dann macht er ganz normal Induktion.

Aber die Schritte da oben sind irgendwie komisch, weil er nicht erklärt, wie er das gewählt hat. Er hat einfach log umgeschrieben fertig.

log_xb = log_ax/(log_ab)

---

In der Ungleichung

        \(\log_a n \leq n\)

hängt das \(N\), ab dem die Ungleichung für alle \(n \geq N\) erfüllt ist, von \(a\) ab. Hat man aber für jedes \(a\) so ein \(N\) gefunden, dann ist \(O(\log_a n) \leq O(n)\) bewiesen. Und zwar wohlgemerkt mit Wahl von \(c = 1\).

Es könnte sich als schwierig erweisen, für jedes \(a\) ein geeignetes \(N\) zu finden. Deshalb sucht man zunächst nur ein \(N\) für den Fall \(a=2\). Hier ist \(N=0\) eine geeignete Wahl. Man zeigt also zunächst nur die Ungleichung

        \(\log_2 n \leq n\)

für alle \(n\geq 0\). Und zwar auch hier wohlgemerkt mit Wahl von \(c=1\). Das ist vermutlich der Teil wo ihr vollständige Induktion angewendet habt.

Mit Basiswechel (siehe Satz unten) kann man dann argumentieren: Für alle \(n \geq 0\) gilt

        \(\begin{aligned} &  & \log_{2}n & \leq n &  & |:\log_{2}a\\ & \implies & \frac{\log_{2}n}{\log_{2}a} & \leq\frac{1}{\log_{2}a}\cdot n &  & \text{Basiswechsel}\\ & \implies & \log_{a}n & \leq\frac{1}{\log_{2}a}\cdot n\end{aligned}\)

Damit ist \(O(\log_a n) \leq O(n)\) bewiesen mit Wahl von \(c = \frac{1}{\log_2 a}\) und \(N = 0\).

Satz (Basiswechsel). Seien \(p,q>0\) mit \(p\neq1\) und \(q\neq1\) und \(r>0\). Dann ist

        \(\begin{aligned} \log_{p}r & =\frac{\log_{q}r}{\log_{q}p} \end{aligned}\)

Beweis. Sei \(x\in\mathbb{R}\) mit \(p^{x}=r\). Dann gilt einerseits

        \(\begin{aligned} p^{x} & =r &  & |\log_{p}\\\log_{p}\left(p^{x}\right) & =\log_{p}r &  & \text{Def. Logarithmus}\\ x & =\log_{p}r \end{aligned}\)

und andererseits

        \(\begin{aligned} p^{x} & =r &  & |\log_{q}\\ \log_{q}\left(p^{x}\right) & =\log_{q}r &  & \text{3. Logarithmusgesetz}\\ x\log_{q}p & =\log_{q}r &  & |:\log_{q}p\\ x & =\frac{\log_{q}r}{\log_{q}p} \end{aligned}\).

Also ist auch

        \(\log_{p}r=\frac{\log_{q}r}{\log_{q}p}\qquad\qquad\qquad\qquad\qquad\qquad\square\)

Dieser Satz besagt, dass sich die Funktionen

        \(x\mapsto \log_p x\)

und

        \(x\mapsto \log_q x\)

nur um den konstanten Faktor \(\frac{1}{\log_q p}\) unterscheiden.

log_xb = log_ax/log_ab

Das stimmt so nicht. Schau noch mal in den Satz zum Basiswechsel rein.