How to find the complexity of T(n)=T(sqrt(n)) + 1 ?

Question

Please tell me the complete steps how to solve this problem.

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

Comments

https://gateoverflow.in/11211/how-to-find-the-complexity-of-t-n-t-sqrt-n-1

---

$T(2) = 1$

What I don’t understand is how can we make such approximations? How can we validate this is true?

Answer 1

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)$

Comments

are you sure?? because I have seen in a book that wrote we can solve this by master method also. However the book solved this by substitution. It is a study material from ACE.

---

http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf

http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem.pdf

for your confirmation.

---

Yes, you are right. It can be done using M.T.

Answer 2

log (logn)

u can find it by back subsitution method

Comments

Can you please let me know why u took n^(1/2^k)=2

---

it is base condition ....in question base condition will be given to you..i found same question with t(4)=1..in that case i will take n^(1/2^k)=4..in that case

1/2^k(log n base 2)=log 4 base 2

1/2^k=2/logn base 2

2^k=lod n base 2 /2

2^k-1=log n base 2

k=log(log n)+1

will equvilent to log(log n)

---

How is the base case set to  n^(1/2^k)=2? Why can't It be n^(1/2^k)=1?

---

its not necessary to take 2. you can take any value >1. You cant take 1 because then when you take log the rhs becomes 0 and then you wont find any relation between k and n.

Answer 3

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

Answer 4

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)...