Wenn du denkst, dass die Aussage nicht gilt, versuche ein Gegenbeispiel zu finden.
Selbstständig, Punkte: 30.55K
Betrachte die Funktionen f, g, h : N → R.
Zeige oder widerlege:
f(n) ∈ Θ(g(n)) ∧ g(n) ∈ O(h(n)) ⇒ f(n) ∈ Θ(h(n))
Könnte mir Jemand dabei helfen?
(Θ-Notation). Seien f, g : N → R, dann gilt
f ∈ Θ(g) :⇔∃c1, c2 ∈ R>0 : ∃n0 ∈ N>0 : ∀n ∈ N≥n0:
0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)
Man sagt, f wächst asymptotisch in derselben Größenordnung wie g.
(O-Notation). Seien f, g : N → R, dann gilt
f ∈ O(g) :⇔∃c ∈ R>0 : ∃n0 ∈ N>0 : ∀n ∈ N≥n0:
0 ≤ f(n) ≤ cg(n)
Man sagt, f wächst höchstens in derselben Größenordnung wie g