Time Complexity of T(n)=T(n^1/3)+lg n .

Hi.How can I find Time Complexity of this equation T(n)=T(n^1/3)+lg n .

Parth Sharma @parthsharmau
4 Aug 2016 09:01 am

T(n)=T(n^1/3) + logn

let n=2^m

T(2^m)=T(2^m/3) + log 2^m

again let  T(2^m)=S(m) 

then T(2^m/3) becomes S(m/3)


S(m)= S(m/3) + log m

we can easily solve this using masters method 

Alireza @alireza
4 Aug 2016 10:38 am
thank you again,very helpful
Habib Mohammad Khan @habibkhan
13 Aug 2016 11:38 am

Mr. Parthsharma ,the substitution you have done is not correct and complete.Let n = 3k.So log3n  = k and n1/3 = 3k/3.So the given recurrence becomes S(k) = S(k/3) + k which on solving gives Ø(k) = Ø(log3n) .Hence Ø(log3n) is the answer.So in your recurrence S(m) = S(m/3) + logm it should be m not logm.

Arjun @arjunsinghra
13 Aug 2016 01:30 pm

see the solution of above question


n=2m where m=log2n


Let T(2m)=S(m) and T(2m/3) =S(M/3)

so  S(m)=S(m/3)+m

using master theoram 3rd case appled becase a<bk where a=1 ,b=3,k=1,p=0

time complexity is O(m)

after subtitution the time complexity is O(logn)