Question

Complexity of T(sqrt(N)) + log N

Comments

T(n)=T(√n)+log n ??

Answer 1

Given, $T(n) = T(\sqrt[2]{n}) + log n$

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

$T(2^k) = T(n^{\frac{k}{2}}) + log (2^k)$

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

$S(k) = S(\frac{k}{2}) + k $

Now this can be solved easily by Master theorem (3rd Case),

$S(k) = k $

so, $T(n) = log n $

Comments

3rd case of Master theorem requires regularity check also..

---

Yes sir, but i have left that for the person who have asked the question, I have just mentioned the 3rd case will be applicable here, I have not applied that. I have just written the answer.

Answer 2

T(n)=T(√n)+logn

n=2^m

T(2^m)=T(n)=S(m)

 T(√n) =S(m/2) 

logn=log 2^m =m

S(m)=S(m/2)+m

By masters Theorem 

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

case : a<b^k

Therefore T(n) =O(n^klog^pn)

S(m)=O(m)

T(2^m)=O(m)

since 2^m =n =>m=logn

T(n)=O(m)=O(logn)

Therefore T(n)=O(logn)