Gate 2017 Algorithm Time Complexity of the recurrence relation

Time complexity?

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

       =2, 0<n<=2

5Comments
abhinandan @abhinandan
22 Feb 2017 09:17 pm

answer would be logn.. to solve such question take n=2^m.. and proceed further and apply master's theorm

Jaya @jaya1
24 Feb 2017 09:47 pm

log (log n) is the answer ?

abhinandan @abhinandan
14 Mar 2017 06:54 pm

nope log(n) is the answer

Akash @akashdinkar
16 Mar 2017 09:29 pm
Answer must be log(n).....
shivanisrivarshini @shivanisrivarshini
22 Mar 2017 04:33 pm

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

let 2^m =n  --------- i

T(2^m)=2T(2^m/2)+1

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

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

By solving this through masters theorem S(m)=O(m)

i.e T(2^m)=O(m)

m=log n          from  i

Therefore T(n)=O(log n)