We are asked the time complexity which will be the number of recursive calls in the function as in each call we perform a constant no. of operations and a recursive call. The recurrence relation for this is (considering constant time "$c$" as $1$)
$T(n) = T(\sqrt n) + 1$
$= T\left(n^{1/4}\right) + 2 \\=T\left(n^{1/8}\right) + 3 $
Going like this we will eventually reach $T(3)$ or $T(2)$. For asymptotic case this doesn't matter and we can assume we reach $T(2)$ and in next step reach $T(1)$. So, all we want to know is how many steps it takes to reach $T(1)$ which will be $1+ $no. of steps to reach $T(2)$.
From the recurrence relation we know that $T(2)$ happens when $n^{\left(\frac{1}{2^k}\right)} = 2$.
Taking $\log $ and equating,
$\frac{1}{2^k} \log n = 1 \\2^k = \log n \\k = \log \log n$.
So, $T(1)$ happens in $\log \log n + 1$ calls, but for asymptotic complexity we can write as $\Theta \left( \log \log n\right)$
Alternatively,
Substituting values
$T(1) = 1$
$T(2) = 1$
$T(3) = T(1) + 1 = 2$
$\dots$
$T(8) = T(2) + 1 = 2$
$T(9) = T(3) + 1 = 3$
$\dots$
$T\left(\left({\left({2^2}\right)^2}\right)^2\right) = T\left(\left({2^2}\right)^2\right) + 1 \\= T(2^2)+ 2 \\= T(2) + 3 = 1 + 3 = 4, \\ \log \log n = 3 \text{ as } n = 256$.
$T\left(\left({\left({\left({\left({2^2}\right)^2}\right)^2}\right)^2}\right)^2\right) = 6,\\ \log \log n = 5 \text{ as } n = 65536 \times 65536 = 2^{32}$
$T\left(2^{(2^{10})}\right) = T\left(2^{512}\right) + 1 \\= T(2^{256}) + 2 \\= T(2^{128}) + 3\\ = T(2^{64}) + 4 \\= T(2^{32}) + 5 \\= T(2^{16}) + 6 \\= T(2^8)+7 \\= T(2^4) + 8 \\= T(2^2) + 9 \\= T(2) + 10 = 11,\\ \log \log n = 10$
So, answer is D
http://stackoverflow.com/questions/16472012/what-would-cause-an-algorithm-to-have-olog-log-n-complexity