Beweise Sie folgende Behauptungen der O-Notationen

Question

Beweisen Sie folgende Behauptungen:

1. x^a = O(x^b) genau dann, wenn a − b <=0.

2. log_a(x) =θ (log_b(x)) für alle a, b.

3. a^x = Ο(b^x) genau dann, wenn 0<=a<=b.

Jetzt bin etwas irritiert. Ich hab bei der 1. Aufgabe einfach die Definition |f(x)|<= c* |g(x)| genommen und für c eben x^a-b herausbekommen. Ist das nun der Beweis, oder muss ich noch was machen?

Comments

\(c\) soll eine Konstante sein, also ist die Wahl \(x^{a-b} \) ziemlich sinnfrei.

---

Kannst du mir dann sagen, wie ich das machen soll?

---

Betrachte $$ \lim \limits_{x \to \infty} x^{a-b} $$

und überlege dir wann ein Grenzwert existiert und was das mit deiner Aufgabe zu tun hat.

---

Ich weiß, dass klingt jetzt blöd, aber von Grenzwerten war in der Vorlesung nie die Rede, und im Skript gibt es das auch nirgendwo. Deswegen muss ich dich fragen wie du gerade auf den Bruch kommst?

---

Habe es editiert.

Dann schreib doch mal ausführlich eure Definition auf.

---

- R(n) =Ω (f(n)), falls es von n unabhängige Konstanten c₁; n₁ gibt mit

R(n)>=c₁f(n)  für Alle n>=n₁:

- R(n) = O(f(n)), falls es von n unabhängige Konstanten c₂; n₂ gibt mit

R(n)<= c2f(n)  für Alle n>=n2:

- R(n) =Θ (f(n)), falls R(n) = Ω(f(n)) ∧ R(n) = O(f(n))

Das ist unsere Definition

Answer 1

das mit dem Grenzwert werdet ihr bestimmt dann noch behandeln. Mit deiner Definition betrachte folgende Überlegungen:

1) Für \(a \leq b \) ist $$ x^{a-b} \leq 1 $$ für \( x \geq 1 \)

2) Für \(a > b \) ex. für jedes \(c \in \mathbb{R} \) ein \(x \in \mathbb{R} \) mit

$$ x^{a-b} \geq c $$

Gruß