Lösen Sie die Rekurrenzgleichung mit Hilfe eines Rekursionsbaumes

Question

Aufgabe:

Lösen Sie die Rekurrenzgleichung

$$ \begin{aligned} T(n) &=3 T\left(\frac{n}{3}\right)+n \text { für alle } n \geq 3 \\ T(1) &=1 \end{aligned} $$

mit Hilfe eines Rekursionsbaumes. Nehmen Sie zur Vereinfachung an, dass \( n \) eine Potenz von 3 ist.

Answer 1

Mathematisch sicher nicht sauber formuliert, aber ich probiere das mal. Vielleicht kann es ja jemand verbessern und ergänzen.

T(n) = 3 * T(n/3) + n = 2*3 für n = 3

T(n) = 3 * (3 * T(n/9) + n/3) + n = 9 * T(n/9) + 2n = 3*9 für n = 9

T(n) = 9 * (3 * T(n/27) + n/9) + 2n = 27 * T(n/27) + 3n = 4*27 für 9 = 27

.....

T(n) = (log3(n) + 1) * n

T(n) = n * log3(n) + n für eine 3er-Potenz n