Question 9704 – Time-Complexity

 Procedure A(n)
  If n <= 2 return(1) else return (A(⌈√n⌉)); 

T(n) = T(√n)+1
Let n=2^m
So, T(2^m) = T(2^m/2)+1
We substitute T(2^m) = S(m),
So now the equation becomes,
S(m) = S(m/2)+1
Now after applying master’s theorem,
S(m) = O(log m)
T(n) = O(log log n)