O-Kalkül: Beweisen oder widerlegen Sie

Question

Gegeben sind die Funktionen f1, f2 ∈ O(n). Beweisen oder widerlegen Sie:
f1 ∉ O(f2) ⇒ f2 ∈ O(f1) 

Wie kann man das beweisen?

Comments

Kann ich hier so herangehen, dass ich sage f1 = 1 und f2 = log n und daher stimmt die Aussage nicht?

---

Durch f₁(n) = 1, f₂(n) = log n  ist die Prämisse f₁ ∉ O(f₂) nicht erfüllt.

Answer 1

Wie kann man das beweisen?

Das kann man nicht beweisen. Das kann man nur widerlegen, zum Beispiel durch

        f₁ (n) := ((-1)ⁿ +1) · n

        f₂ (n) := ((-1)ⁿ⁺¹ +1) · n