Master Theorem (VL 05) Flashcards
1
Q
Allgemeines Format der Rekursionsgleichung
A
T(n) = b · T(n / c) + f(n)
2
Q
Erster Fall M1 des Master Theorems
A
f(n) ∈ O( n^(E-ε) ) für ein ε > 0
3
Q
Zweiter Fall M2 des Master Theorems
A
f(n) ∈ Θ( n ^E )
4
Q
Dritter Fall M3 des Master Theorems
A
f(n) ∈ Ω( n^(E+ε) ) für ein ε > 0 und wenn bf(n/c) ≤ df(n) für ein d < 1 und n hinreichend groß
5
Q
Wenn M1: f(n) ∈ O( n^(E-ε) ) für ein ε > 0, dann…
A
T(n) ∈ Θ( n ^E )
6
Q
Wenn M2: f(n) ∈ Θ( n ^E ), dann…
A
T(n) ∈ Θ( n ^(E) * log n)
7
Q
Wenn M3: f(n) ∈ Ω( n^(E+ε) ) für ein ε > 0 und wenn bf(n/c) ≤ df(n) für ein d < 1 und n hinreichend groß, dann…
A
T(n) ∈ Θ( f(n) )
