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) // eventually
replace k with log n to the 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)