Trying to work out the following question, but I'm stuck.. Can someone direct me please.
Using a change of variables
$ \text{Let}\ m = \lg\ n \\ S (m) = T (2m)\\ T (2^{m}) = T (2^{m/2}) + 2 \\ S( m) = S (m/2) + 2 $
Using Master Theorem
$ n\ log_b a = n\ log_2 1 = n^{0} = 1\text{ and }f (n) = 2 $
Since $ 1 < θ(2)$, case 1 applies and $S (m) = θ(\lg\ m^2), \quad\therefore T (n) \in \theta(\lg\lg{n^2}) $
or
I was also thinking about the problem like this: $\begin{align} T(n) &= T(\sqrt n ) + 2 = T(n^{1/2}) + 2 = T(n^{1/4}) + 4 = \cdots \\ &= T(n^{1/2^i}) + 2i = \cdots = T(n^{1/2^k}) + 2k\\ \end{align}$ $ n^{1/2^k} <=2 \\ \text{so } \log n = 1/(2^k) \\ k = \log (\frac{1}{\log n}) $ $ ∴ T (n) ∈ θ(\lg \lg n)\ or\ T(n)\ \in θ(\log (\frac{1}{\log n})) $