Aufgabe O-Notation (Uni)

Question

Für die Aufgabenteile e) & \( \mathrm{f} \) ) betrachten wir Logarithmen als Funktionen von \( \mathbb{N} \) nach \( \mathbb{R} \). Weiter seien \( a, b \in \mathbb{R}_{>0} \backslash\{1\} \) und \( a>b . \) Sie dürfen, falls nötig, die üblichen Rechenregeln für Logarithmen verwenden. Zeigen oder widerlegen Sie:

(a) \( n^{2}+2 n+1=O\left(n^{2}\right) \)

(b) \( (n+1)^{3}=O\left(n^{3}\right) \)

(c) \( 2^{n}=O(n !) \)

(d) \( \log _{a}(n)=O\left(\log _{b}(n)\right) \)

(e) \( \log _{b}(n)=O\left(\log _{a}(n)\right) \)

Also ich habe bei

a) \( \frac{ n^2+2n+1}{n^2} \) = \( \frac{n^2}{n^2} \) + \( \frac{2n}{n^2} \) +  \( \frac{1}{n^2} \) ≤ 1 + 2 + 1 ≤ 10 (irgendeine Zahl)

Bei

b) (n + 1)³ = n³ +3n² +3n +1 = O(n³)

=  \( \frac{ n^3+3n^2 +3n +1}{n^3} \) = \( \frac{n^3}{n^3} \) + \( \frac{3n^2}{n^3} \) +  \( \frac{3n}{n^3} \) +  \( \frac{1}{n^3} \) ≤ 1 + 3 + 3 + 1 ≤ 10 (irgendeine Zahl)

Bei c)

\(( \frac{2}{2})^\frac{n}{2} \) * 2^{\( \frac{2}{2} \)}  =  \(( \frac{2}{2}^2)^\frac{n}{2} \)  = \( \frac{2}{n/2}^n \) (also falsch)

Ist das korrekt und weiß jemand, wie man d) und e) zeigen oder widerlegen soll?

Answer 1

Hallo:-)

Deine Rechenwege sind keine Beweise. (a), (b) , (c) und (e) sind wahr. (d) ist falsch.

Ich schreibe mal die ,,übliche" Landau-Definition für groß-O hin:

$$ \mathcal{O}(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ \underbrace{0\leq f(n) \leq \alpha \cdot g(n)}_{0\leq f(n) \ \land f(n)\leq \alpha\cdot g(n) }  \} $$

Du musst also eine Konstante \(\alpha>0\) und eine Stelle \(n_0 \in \mathbb{N}\) finden, sodass für alle \( n\geq n_0\) die Ungleichung \(0\leq f(n)\leq \alpha\cdot g(n)\) gilt.

Nebenbei bemerkt ist die Schreibweise \(f=\mathcal{O}(g)\) absolut falsch. \(\mathcal{O}(g)\) ist eine Menge! Sie beschreibt doch, die Menge aller Funktionen \(f:\ \mathbb{N}\rightarrow \mathbb{R}\), die bis auf eine Konstante höchstens so schnell wie \(g\) wachsen. Die Schreibweise \(f\in \mathcal{O}(g)\) ist von daher korrekt.

Ich führe mal den Beweis für die Definition bei (a) vor:

Es ist \(n^2+2n+1\in \mathcal{O}(n^2)\) zu zeigen. Dabei ist \(f(n)=n^2+2n+1\) und \(g(n)=n^2\).

Ich suche also eine Konstante \(\alpha>0\) und eine Stelle \(n_0 \in \mathbb{N}\), sodass für alle \( n\geq n_0\) die Ungleichung \(0\leq \underbrace{n^2+2n+1}_{=f(n)}\leq \alpha\cdot \underbrace{n^2}_{=g(n)}\) gilt.

Entweder man sieht bereits, welche Konstante \(\alpha>0\) und Stelle \(n_0\in \mathbb{N}\) zu verwenden sind, denn dann kannst du mit Induktion die Ungleichung zeigen. Oder man bekommt diese durch geschicktes Abschätzen mitgeliefert. Ich wähle letzteres:

$$ \begin{aligned}&n^2+2n+1\\\stackrel{n\geq 2}{\leq} &n^2+n^2+1\stackrel{n\geq 2}{\leq} &n^2+n^2+n^2=3\cdot n^2\end{aligned} $$

Also wähle ich \(\alpha=3\) und \(n_0=2\). Damit ist \(n^2+2n+1\in \mathcal{O}(n^2)\).

Comments

Wow danke. Kannst du vielleicht noch die Beweise von b) und c) kurz zeigen? Die anderen habe ich schon

---

b) kannst du analog wie a) machen und c) zeige durch Induktion die Ungleichung \(2^n\leq n!\) für alle \(n\in \mathbb{N}_{\geq 4}\).

---

Also bei b) auch dieselben Werte für die Konstante und n?

---

Nein. Du sollst durch Abschätzen auf die Werte für n und α kommen.

---

Bei b) Könnte ich für die Konstante den Wert 25 geben und für n = 3 dann wäre das richtig beispielsweise

---

Ja, das geht auch. Das kannst du durch Induktion zeigen oder du zeigst es durch geschicktes Abschätzen.

---

Ah, ich hab's. Für die Konstante 3 und für n=1

---

Okay, ich würde aber lieber die 3 und die 1 benutzen

---

Was ist 3 und was ist 1?

---

Konstante = 3 und n = 1

---

Das funktioniert nicht. Wenn dann n=3, wenn du α=3 wählst. Aber nun musst du die entsprechende Ungleichung beweisen.

---

Sprechen wir von derselben Aufgabe b) mit n^3? Stimmt, du hast Recht

---

Genau. Mache einfach eine Induktion.

---

aber im letzten Schritt wäre n^3 + n^3 +n^3 + n^3 Ungleich 3 * n^3

---

Was rechnest du überhaupt gerade?

---

alles gut, danke für die Hilfe