UPPCL 2018 AE

Question

Time complexity of this Recurrence relation 

T(n)=T(√n) +1

• A. O(nlogn)
• B. O(log log n)
• C. O(n^2)
• D. n^2 logn

 

Comments

option B

---

if you didn't provide explanation, make it as comment but not as answer !

Answer 1

Answer is B.

You can do back substituting, $T(n) = T(n^{1/2}) + 1 = (T(n^{1/4})+1) + 1 = ((T(n^{1/8})+1)+1) + 1$

In general, we will get, $T(n)= T(n^{\frac{1}{2^k}}) + k$

Now we will back substitute till the recursive term is eliminated, assuming T(2) to be const.

i.e.  $n^{\frac{1}{2^k}} = 2$, take log on both sides, $2^k = log n$, again take log on both sides, and you will get $k = log log n$

thus $T(n)= O(log log n)$