Ich habe ein Problem beim Auflösen der folgenden Rekurrenzgleichung:
T(n) = 9 * T(n/3) + n^2 mit n = 3^k und T(1) = c
Mit dem Master-Theorem komme ich auf T(n) € Theta(n² * log n).
Per Hand komme ich auf T(n) € O(n²). Sieht jemand einen Fehler bei der Lösung:
T(n) = 9 * T(n/3) + n^2
<-> T(n) = 9 * (T(n/9) + n²/9) + n²
<-> T(n) = 9 * T(n/9) + n² + n²
<-> T(n) = 9 * [ T(n/27) + 1/81 n²] + n² + n² = 9 * T(n/27) + 1/9 n² + n² + n²
<-> T(n) = 9* [ T(n/81) + n²/729] + 1/9 n² + n² + n²
<-> T(n) = 9 * T(n/81) + n²( 1/81 + 1/9 + 1) + n²
=> T(n) = 9 * T(n/3^i) + n² * Summe_j=0...(i-1) [ 1/9^j ] + n²
... bis i = k = log_3(n)
T(n) = 9 * T(1) + n² * Summe_j=0...(k-1) [(1/9)^j] + n²
<-> T(n) = n² + 9c + n² [(1-(1/9)^k) / (1 - 1/9)]
<-> T(n) = n² + 9c + n²*9/8 * [1-1/(9^k)]
für n -> inf geht 1/9^k gegen 0 und somit
T(n) -> n² + 9c + n²*9/8 € O(n²)
Was mache ich falsch?
