retagged by
18,585 views
4 votes
4 votes
the solution of recurrence relation

T(n)=2T(floor(sqrt(n))+log n
retagged by

1 Answer

Best answer
15 votes
15 votes

T(n)=2T(⎷n)+logn

Let n=2k

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

Let T(2k)=S(k)

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

Using Master Theorem

S(k)=O(k log k)

So T(n)=O(logn log logn)

selected by

Related questions

0 votes
0 votes
1 answer
1
lucasbbs asked Feb 28, 2022
6,573 views
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...
3 votes
3 votes
2 answers
2
Tony Bayan asked Jun 4, 2016
12,308 views
1 votes
1 votes
2 answers
3
mdboi asked Oct 28, 2022
735 views
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n