Question

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

1. \( T(1)=2, T(n)=T\left(\frac{n}{2}\right)+n \)

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

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

Ansatz:

Für 1. dachte ich mir:

a=1 , b= 2 , c=1

log₂ 1 = 2 > 1 ... ?

Comments

zu 3:

a=4, b=2 , c=3  ---> Θ(n³)