Geben sie mit Hilfe des Master-Theorems die asymptotischen Schranken an

Question

Geben Sie mit Hilfe des Master-Theorems gute asymptotische Schranken für die folgenden Rekursionsgleichungen an.

a) \( T(1)=1, T(n)=4 \cdot T\left(\frac{n}{2}\right)+n \)

b) \( T(1)=1, T(n)=4 \cdot T\left(\frac{n}{2}\right)+n^{2} \)

c) \( T(1)=1, T(n)=4 \cdot T\left(\frac{n}{2}\right)+n^{3} \)

Answer 1

Als erstes muss man die Laufzeitklasse der Aufwandsfunktion bestimmt werden:

Das Mastertheorem lässt sich für eine Rekurrenz T 

T(n) = a*T(n/b) + f(n)

anwenden, wenn eine der folgenden Bedingungen erfüllt ist:

i) f ∈ Ο(n^log_b(a)-e) für ein e > 0

ii) f ∈ Θ(n^log_b(a))

iii) f ∈ Ω(n^log_b(a)+e) für ein e > 0 und für ein c∈]0, 1[: af(n/b) ≤ c*f(n)

 

In jedem der Beispiele ist a=4, b=2, also muss das Verhältnis zwischen f und n² bestimmt werden.

a) Für ε=1 gilt:

f∈ O(n^2-1) = O(n)

Damit gilt:
T ∈ Θ(n²)

b) Es gilt f ∈ Θ(n²)

Also:

T ∈ Θ(n² log(n))

c) Es gilt f∈ Ω(n³) mit ε=1. Nun muss noch die zusätzliche Bedingung erfüllt sein:
4*(n/2)³ ≤ c*n³

1/2 n³ ≤ c*n³

Offenbar tut zum Beispiel c = 1/2 den Job.

Damit folgt: T ∈ Θ(f(n)) = Θ(n³)