Beweisen mit Hilfe der O-Notation

Question

Aufgabe:

Beweisen sie folgenden Aussagen mithilfe der O-Notation:

a) 2n³+7n - 2 ∈  O(n³)

b) 2^3+log2n ∈ O(n)

_{c) n*2}^(2+log(2n))  ∈ Omega(n²₎

Problem/Ansatz:

2n³+7n - 2 <= c * n³     Wähle n =  1

2*1+7*1 -2 <= c * 1³

7 <= c                            c ist >= 7

2^3+log2n  <= c * n    wähle n = 1

2^3+log2*1 <= c * 1

2^3+log2 <= c

Ist die erste Aufgabe soweit richtig und die zweite Aufgabe kann ich das c so wählen das >= 2^3+log2 ist oder muss ich da noch was umformen?

Answer 1

c ist >= 7

Du hast ein geeignetes \(c\) gefunden.

Du hast aber nicht bewiesen, dass mit dieser Wahl von c

        \(2n^3+7n - 2 \leq c \cdot n^3\)        für alle \(n \geq 1\)

ist.

Comments

Was genau fehlt den?

Ist damit nicht bewiesen das die Ungleichung gilt wenn ich ein geeignetes c habe und n das ich diese dann einsetze und dann die Ungleichung gilt?

---

Du hast bewiesen: Wenn \(n = 1\) ist, dann ist bei der Wahl von \(c=7\)

        \(2n^3+7n - 2 \leq c \cdot n^3\).

Du musst beweisen: Wenn \(n \geq 1\) ist, dann ist bei der Wahl von \(c=7\)

        \(2n^3+7n - 2 \leq c \cdot n^3\).

Beispiel warum deine Rechnung nicht ausreicht, ist

        \(f(n)=2n^3-6n^2+5n\in O(n^3)\).

Laut deinem Ansatz:

\(\begin{aligned} 2n^{3}-6n^{2}+5n & \leq c\cdot n^{3} & \text{Wähle }n=1\\ 2\cdot1-6\cdot1+5\cdot1 & \leq c\cdot1^{3}\\ 1 & \leq c & c\geq1 \end{aligned}\)

Allerdings ist

        \(f(6) = 2\cdot6^3-6\cdot6^2+5\cdot6=246 \nleq 216 = 1\cdot 6^3\)

Stattdessen: Für alle \(n\geq 1\) gilt

        \(\begin{aligned} & 2n^{3}-6n^{2}+5n\\ \leq\ & 2n^{3}+5n\\ \leq\ & 2n^{3}+5n^{3}\\ =\ & 7n^{3}\text{,} \end{aligned}\)

also ist

        \(f(n)=2n^3-6n^2+5n\in O(n^3)\).

---

HI vielen dank für die Antwort,

aber ich frage mich

Stattdessen: Für alle \(n\geq 1\) gilt         \(\begin{aligned}  & 2n^{3}-6n^{2}+5n\\ \leq\ & 2n^{3}+5n\\ \leq\ & 2n^{3}+5n^{3}\\ =\ & 7n^{3}\text{,} \end{aligned}\)

Wie erfolgt die Abschätzung das du aus 5n einfach ein 5n³ ?

Wenn ich ein anderes Beispiel habe:

7n² +25 ∈ O(n²)

Dies ist bewiesen mit n= 5 und c = 8, aber wie kann man da abschätzen weil ich oben bei deine Erklärung noch nicht verstanden habe wie man abschätzen kann

---

Wie erfolgt die Abschätzung das du aus 5n einfach ein 5n³ ?

Mutipliziert man eine positive Zahl \(m\) mit einer Zahl \(n \geq 1\), dann ist das Ergebnis mindestens so groß wie \(m\).

Also ist

        \(5n \leq 5n\cdot n \leq 5n\cdot n\cdot n\)

für alle \(n \geq 1\).

---

7n² +25 ∈ O(n²)

Dies ist bewiesen mit n= 5 und c = 8

Für \(n\geq 5\) gilt \(8n^2 = 7n^2 + 1n^2 \geq 7n^2 + 1\cdot 5^2 = 7n^2 + 25\).

---

K vielen Dank!

Das heißt

7n^2 + 25 <= 8n^3

Damit wäre das ja bewiesen