algorithm - Solving the similar recurrence: T(n) = 3T(n/3) + n/3 -

given..

t(0) = 3 n <= 1  t(n) = 3t(n/3) + n/3 n > 1 

so answer's suppose o(nlogn).. here's how did , it's not giving me right answer:

t(n) = 3t(n/3) + n/3  t(n/3) = 3t(n/3^2) + n/3^2 

subbing t(n) gives..

t(n) = 3(3t(n/3^2) + n/3^2) + n/3  t(n/3^2) = 3(3(3t(n/3^3) + n/3^3) + n/3^2) + n/3 

eventually it'll like..

t(n) = 3^k (t(n/3^k)) + cn/3^k 

setting k = lgn..

t(n) = 3^lgn * (t(n/3^lgn)) + cn/3^lgn  t(n) = n * t(0) + c  t(n) = 3n + c 

the answer's o(n) though..what wrong steps?

t(n) = 3t(n/3) + n/3 t(n/3) = 3t(n/9) + n/9  t(n) = 3(3t(n/9) + n/9) + n/3      = 9t(n/9) + 2*n/3      //statement 1  t(n/9)= 3t(n/27) + n/27 t(n)  = 9 (3t(n/27)+n/27) + 2*n/3 // replacing t(n/9) in statement 1       =  27 t (n/27) + 3*(n/3)  t(n)  = 3^k* t(n/3^k) + k* (n/3) // 

replace k log n base 3.

t(n)  = n t(1) + (log n) (n/3); // t(1) = 3 t(n)  = 3*n + (log n) (n/3); hence , o (n* logn)