Can anyone please solve this recurrence

T(n)=T(3√n)+logn.T(n)=T(3\sqrt n)+\log n.

It came in my paper. I want to know whether the following answer is right or wrong:

My answer: T(n)=log3n.T(n)=\log^3 n.

=================

1

I am tempted to say: yes, the result is log(n)3\log(n)^3, that’s all. Besides, what do you mean when you say “it came in my paper” ?

– JeanMarie

2 days ago

=================

1 Answer

1

=================

For n=9n=9 the recurrence T(n)=T(3√n)+lgnT(n)=T(3\sqrt n)+\lg n gives

T(9)=T(9)+lg9T(9)=T(9)+\lg 9,

hence lg9=0\lg9=0 ??

Something wents wrong …

This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. – From Review

– Daniel R

2 days ago

What the OP has in mind is an asymptotic behavior. The word “recurrence” is maybe misleading: this is the way it is also named in complexity analysis of algorithms

– JeanMarie

2 days ago

Sorry for the typing confusion

– Saurav Pandey

14 hours ago

T(3âˆڑn) means cube root of n

– Saurav Pandey

14 hours ago