Question

What is the complexity of T(n) =T(sqrt(n)) +loglogn

Comments

is it (loglogn)^2 ?

---

Yes

Can be written as log^2logn

Answer 1

Given, $T(n)=T(√n)+loglogn$

Let consider $n=2^k$  then recurrence equation will be

$T(2^k)=T(n^{k/2})+loglog(2^k)$

Now lets consider $T(2^k)=S(k)$ then the recurrence relation will be

$S(k)=S(k/2)+logk$

Now this can be solved easily by Master theorem

By masters Theorem

$a=1$ $b=2$ $k=0$ $p=1$

2nd Case( $| |$ )case : $a=b^k$

$S(k) = loglogk $                              //$ k=logn$

so, $T(n)=logloglogn$

Comments

$ T(n)=T(√n)+loglog(n) $

Let $ n=2^k$

recurrence equation will be

$T(2^k)=T(2^{k/2})+loglog(2^k)$

Let $T(2^k)=S(k)$

So $S(k)=S(k/2)+log (k)$

By masters Theorem

$ a=1 , b=2, f(k)= log (k) $

2nd Case Master theorem not possible. It's 3rd case because here $ f(k)= log (k )$ is greater than $k^{log _{b}^{a}}=k^{log_{2}^{1}}=k^0$ but not polynomial time.

So,

$S(k)$ = $\Theta$$(k^0 * log( k)^{1+1})$=$\Theta$ $(log^{2} k)$

Replacing all values with T(n) and its equivalent and k= log n.

So $T(n)$ = $\Theta(log^{2}log(n))$.    //k=log(n).