Rekurrenzen lösen mit Mastertheorem?

Setze n = 4^k

T(4^0) = 1

T(4^k) = 4 * T( (2^2)^k / 2) + wurzel 3* (2^k)^2 + 1

= 4*T(2^(2k-1)) + 2^k * wurzel 3 + 1

???

Answer 1

[eterneladam]

Geht es um eine exakte Lösung oder Anwendung des Master Theorems zur Abschätzung?

Im letzteren Fall hat man

a=4,

b=2,

f(n) =Wurzel(3n)+1 = O( n^(2-epsilon) )

Damit ist T1(n) in Theta( n^2 )

Comments

[rosesarerosie4]

Wurzeln(3n) = (3n)^1/2

Wie kommst du auf n^2-epsilon?

[eterneladam]

@rosesarerosie4

n^2-epsilon braucht man im Master Theorem. n^(1/2) wächst langsamer als n^(2-epsilon) für geeignetes epsilon, was du dir selbst überlegen kannst-