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) + 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) + n
T (n) = T (n − 6) + n−3+ n
T (n) = T (n − 9) + n−6+ n−3 + n
Für n = 9 eingesetzt ergebe sich
T (n) = T (9 − 9) + 9−6+ 9−3 + 9
T (0) = T (0) + 3+ 6 + 9
Da laut Basisfall T (0) = 3 gilt, gilt also:
T (0) = 3 + 3+ 6 + 9
Ergäbe also 10,1815, bzw. als allgemeine Gleichung aufgeschrieben
3 + i=0∑n3n
Die Musterlösung sagt jedoch, dass die Lösung
Θ (n 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