Asymptotische Effizienz (VL 02)

Question 1

g ∈ O(f) gdw. (Grenzwert Def.)

Answer 1

lim sup n→∞ g(n)/f(n) = c, c ≥ 0, c != ∞.

Question 2

g ∈ Θ(f) gdw. (Grenzwert Def.)

Answer 2

lim n->∞ g(n)/f(n)=c, 0 < c < ∞

Question 3

g ∈ Ω(f) gdw. (Grenzwert Def.)

Answer 3

lim inf n->∞ g(n)/f(n)=c, 0 < c

Question 4

g ∈ O(f) gdw. (n0 / c Def.)

Answer 4

g ∈ O(f ) gdw. ∃c > 0, n0 mit ∀n ≥ n0 : g(n) ≤ c · f (n)

Question 5

g ∈ Ω(f) gdw. (n0 / c Def.)

Answer 5

g ∈ Ω(f ) gdw. ∃c > 0, n0 mit ∀n ≥ n0 : c · f (n) ≤ g(n)

Question 6

g ∈ Θ(f) gdw. (n0 / c Def.)

Answer 6

∃c1, c2 > 0, n0 mit ∀n ≥ n0 : c1 · f (n) ≤ g(n) ≤ c2 · f (n)