##### 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 .

##### 4Comments
Parth Sharma
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
4 Aug 2016 10:38 am
thank you again,very helpful
Habib Mohammad Khan
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
13 Aug 2016 01:30 pm

see the solution of above question

T(n)=T(n1/3)+logn

n=2m where m=log2n

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

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)