GeeksForGeeks

Question

Find time complexity of below Program?

A(n){

if(n<=1) return;

else

return $A(\sqrt{n})$ ;

}

Answer 1

T(n)=T(n^1/2) + O(1)

T(1)= O(1)

Let n=2^k

T(2^k)=T(2^k/2) +O(1)

T(k)=T(k/2)+O(1)

Using masters theorem,

T(k)=O(logk)

since n=2^k

k=logn

logk=loglogn

Hence T(n)=O(loglogn)

Comments

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

$T(k)=T(k/2)+O(1),$how you got this step?

---

@lakshman 

let F(x)=2^x

than F(x/2)=2^x/2

Answer 2

The Recurrence Relation from the function we get is:

$T(n) = T(n^{1/2}) + C$

$C$: constant time so say ‘$1$’

then,

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

Now,

Lets Assume $n = 2^{t}$,

Therefore, 

$n^{1/2}$ $=$  $2^{t/2}$

Therefore the equation becomes,

$T(2^{t}) = T(2^{t/2}) + 1$

Now, Say there is a function $P(t)$ such that $P(t) = T(2^{t}),$            $….(i)$

So the equation becomes,

$P(t) = P(t/2) + 1$

Now, 

Using masters theorem,

$P(t)=\Theta (\log_{2}t)$

and $P(t) = T(2^{t}) = T(n)$            $from(i)$

So, $T(n) = \Theta (\log_{2}t)$

Now,
$\because  n = 2^{t},$

$ \therefore  t=\log_{2}n$

$ \therefore  log_{2}t=\log_{2}\log_{2}n$

$Hence, T(n)=\Theta (\log_{2}\log_{2}n)$