Can anyone please solve this recurrence
$$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)=\log^3 n.$
Asked
Active
Viewed 51 times
0
-
1I am tempted to say: yes, the result is $\log(n)^3$, that's all. Besides, what do you mean when you say "it came in my paper" ? – Jean Marie Oct 21 '16 at 11:19
1 Answers
-1
For $n=9$ the recurrence $T(n)=T(3\sqrt n)+\lg n$ gives
$T(9)=T(9)+\lg 9$,
hence $\lg9=0$ ??
Something wents wrong ...
Fred
- 77,394
-
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 – Jean Marie Oct 21 '16 at 11:57
-
-