search
Log In
0 votes
358 views
What is the time complexity of the following recurrence relation and step to derive the same

$T(n) = T(\sqrt{n}) + log(logn)$
closed with the note: Query resolved.
in Algorithms
closed by
358 views

1 Answer

3 votes
Take $n=2^m$ then

$T(2^m)=T(2^{m/2})+\log m$

$\implies S(m)=S(m/2)+\log m$

Solve using master's theorem .$S(m)=O(\log ^2 m)=T(2^m)$

Put $m=logn \implies T(n)=(\log \log n)^2$
0
How did you derive the 3rd step, m = $2^{m}$ is understod but how $2^{m/2}$ written as m/2
1
We are not replacing $2^m \;by\; m$  but we are changing function T to S.

$T(2^m)\implies$  function of m.    (S(m))

$T(2^{m/2})\implies$  function of m/2.    (S(m/2))
0
can you please tell me $log^2(logn)$ and $(loglogn)^2$both are same??
0
Yes..same

Related questions

3 votes
1 answer
1
3 votes
1 answer
2
595 views
What will be the time complexity for the following recurrence relation? $T(n) = 8\sqrt{n} T(\sqrt{n})+(log n)^{2}$ According to me it is $\Theta (n(logn)^{3})$ . Please confirm.
asked Jun 16, 2017 in Algorithms Ashish Sharma 3 595 views
0 votes
1 answer
3
323 views
T(n) = T(n/4) + T(3n/4) + n How to solve these type of problems? Can I solve this using master theorm by considering X = T(3N/4) +N THEN T(N) = T(N/4) +X CAN WE SOLVE LIKE THIS? PLEASE HELP
asked Jan 4, 2019 in Algorithms Mayankprakash 323 views
0 votes
1 answer
4
248 views
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
asked Nov 18, 2018 in Algorithms LavTheRawkstar 248 views
...