Aufgabe:
Bestimme eine Lösung der folgenden Rekursionsgleichung in Θ-Notation. Du kannst davon ausgehen, dass n eine Potenz von 9 ist.
T (0) = 3, T (n) = T (n - 3) + \( \sqrt{n} \)
Problem/Ansatz:
Mein Ansatz wäre, jetzt, da n eine Potenz von 9 ist, 9 einzusetzen und zu gucken, was die Rekursionsgleichung berechnet
T (n) = T (n − 3) + \( \sqrt{n} \)
T (n) = T (n − 6) + \( \sqrt{n-3} \)+ \( \sqrt{n} \)
T (n) = T (n − 9) + \( \sqrt{n-6} \)+ \( \sqrt{n-3} \) + \( \sqrt{n} \)
Für n = 9 eingesetzt ergebe sich
T (n) = T (9 − 9) + \( \sqrt{9-6} \)+ \( \sqrt{9-3} \) + \( \sqrt{9} \)
T (0) = T (0) + \( \sqrt{3} \)+ \( \sqrt{6} \) + \( \sqrt{9} \)
Da laut Basisfall T (0) = 3 gilt, gilt also:
T (0) = 3 + \( \sqrt{3} \)+ \( \sqrt{6} \) + \( \sqrt{9} \)
Ergäbe also 10,1815, bzw. als allgemeine Gleichung aufgeschrieben
3 + \( \sum\limits_{i=0}^{n}{3^{n}} \)
Die Musterlösung sagt jedoch, dass die Lösung
Θ (n \( \sqrt{n} \)
wäre. Aber das wäre ja in diesem Fall (n = 9) dann 9*3 = 27. Und nicht 10,1815.
Kann mir jemand bitte kurz sagen, wo ich den Fehler gemacht habe?
LG
