Aufgaben zur O-Notation

Question

Aufgabe:

Die asymptotische Notation erlaubt einige Operationen, andere nicht. Beweisen oder wiederlegen Sie (durch Gegenbeispiel) die folgenden Aussagen unter den Annahmen f₁(n), f₂(n) ∈ O(g₁(n)) und f₃(n) ∈ O(g₂(n))

a) f₁(n) + f₂(n) ∈ O(g₁(n))

b) f₁(n) + f₃(n) ∈ O(g₁(n) + g₂(n))

c) max{f(n), g(n)} ∈ Θ(f(n) + g(n))

d) g(n) + f(n) ∈ Θ(g(f(n)))

e) f₁(n)/f₃(n) ∈ O(g₁(n)/g₂(n)), falls f₃, g₂ > 0 (/ soll hier für den Bruch stehen)

f) d · f₁(n) ∈ O(d · g₁(n)) für festes d ∈ ℝ+

g) h ∈ O(f² + g²) genau dann wenn h ∈ O((f + g)²)