Sougatamoy Biswas @sougatamoy added a Question 12 Feb 2017 Gate 2017 Algorithm Time Complexity of the recurrence relation Time complexity? T(n)=2T(n^(1/2))+1 =2, 0<n<=2 5Comments thumbs up down up0 like 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 up2 liked Log in or register to post comments J Jaya @jaya1 24 Feb 2017 09:47 pm log (log n) is the answer ? up0 like Log in or register to post comments abhinandan @abhinandan 14 Mar 2017 06:54 pm nope log(n) is the answer up2 liked Log in or register to post comments A Akash @akashdinkar 16 Mar 2017 09:29 pm Answer must be log(n)..... up0 like Log in or register to post comments 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) up0 like Log in or register to post comments

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

log (log n) is the answer ?

nope log(n) is the answer

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)