The Gateway to Computer Science Excellence
0 votes
195 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 by (239 points)
closed by | 195 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$
by Boss (11.8k points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,490 answers
195,434 comments
100,667 users