Theta

[LordNecro]

Eine wahrscheinlich unglaublich blöde Frage aber ist

f(n)=Theta(g(n)) äquivalent zu g(n)=Theta(f(n)).

[Lacce]

Ja, das ist äquivalent.

f(n) = \Theta(g(n)) heißt ja gerade, dass beide Quotienten f(n)/g(n) und g(n)/f(n) beschränkt sind. Diese Aussage ist symmetrisch in f und g.

-Thomas

[tonico]

Ja, ich glaub das kann man z.B so zeigen:

Sei f = f(n), g = g(n).

f = ϴ(g)
⇔ ∃ c1, c2, n0 > 0; ∀ n ≥ n0: 0 ≤ c1g ≤ f ≤ c2g
⇔ 0 ≤ c1g ≤ f ⋀ 0 ≤ f ≤ c2g
⇔ 0 ≤ g ≤ (1/c1)f ⋀ 0 ≤ (1/c2)f ≤ g
⇔ ∃ c3=1/c2, c4=1/c1, n0 > 0; ∀ n ≥ n0: 0 ≤ c3f ≤ g ≤ c4f
⇔ g = ϴ(f)

[LordNecro]

gedacht hab ichs mir schon aber war net ganz sicher und da ich das beim 2ten bsp brauche wollt ich mal nachfragen

Danke für die rasche Antwort