edited by
46,879 views
14 votes
14 votes
Please tell me the complete steps how to solve this problem.

$ T(n) = T ( \sqrt n )+ 1$
edited by

5 Answers

Best answer
20 votes
20 votes
For objective exams do:

Since we have a sqrt term, considering only perfect squares and those which are multiple of 2 as that can take care of log.

$T(2) =  1$//assume

$T(2^2) = T(2) + 1 = 2$
$T(2^{2^2}) = T(4) + 1 = 3$
$T\left(2^{2^3}\right) = T(16) + 1 = 4$
$T\left(2^{2^4}\right) = T(256) + 1 = 5$

So, we are getting $T(n) = \lg \lg n + 1 \implies T(n) = O(\log \log n)$
selected by
13 votes
13 votes

log (logn)

u can find it by back subsitution method

edited by
5 votes
5 votes
Given, T(n)=T(√n)+1

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

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

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

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

Now this can be solved easily by Master theorem

so, S(k)=logk

and T(n)= loglogn
1 votes
1 votes
Assume T(2)=1..just some base case

T(n)=T(ROOT(n))+1...when work equivalent to 1 is done root(n) elements left..

Bring back any Number to 2...

Lets say ==16 ...take 1 step  to bring it to 4.

                    Another step to bring 4 to 2

                   And finally T(2)=1...TOTAL=3 STEPS

NOW TAKE ANY NUMBER

18...greater than 16 and less than 32...it will take less than 32 so can say big0 of (32)..or every n follows O(loglogn)...

Related questions

0 votes
0 votes
1 answer
1
3 votes
3 votes
2 answers
2
Tony Bayan asked Jun 4, 2016
12,323 views
0 votes
0 votes
1 answer
3
lucasbbs asked Feb 28, 2022
6,578 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...
4 votes
4 votes
2 answers
4
gmrishikumar asked Nov 22, 2018
11,414 views
T(n) = sqrt(n) * T(sqrt(n)) + n Given solution is O(log log n). But my solution is O(n log log n).'wolframalpha'' shows the answer same as mine. You can find the solution...