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