Betrachte folgende Rekursiongleichung. Ist n eine Dreierpotenz, so ist
T(n) = 2 T(n/3) + 5n
T(1) = 5
Ist n eine Dreierpotenz, so ist
D.h. n = 3^k
n/3 = 3^{k-1}
Nun hast du T_(1) = T_(3^0) = 5
T_(3^1) = 2* T(3^0) + 5*3^1 = 2 * 5 + 15 = 25
T_(9) = T_(3^2) = 2 * T_(3^1) + 5* 3^2 = 50 + 45 = 95
T_(27) = T_(3^3) = 2 * T_(3^2) + 5* 3^3 = 190 + 5 * 27 = ...
usw.
Könnte der Anfang der Rekursion so gemeint sein?
Wenn nicht, wie lautet deine Rechnung für die ersten Paar T-Werte?