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 < \Theta(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 \left(\frac{1}{\log n}\right) $$ $$ ∴ T (n) \in \Theta(\lg \lg n)\ \text{ or }\ T(n)\ \in \Theta\left(\log \left(\frac{1}{\log n}\right)\right) $$
Let $n = a^{2^m}$. Then $\sqrt{n} = a^{2^m/2} = a^{2^{m-1}}$. Letting $T(a^{2^m}) = g(m)$, we get that $$g(m) = g(m-1) + 2 = g(m-2) + 2 + 2 = g(m-3) + 2 + 2 +2 = g(0) + 2m$$ Note that $$\log_2(n) = 2^m \log_2(a) \implies \log_2(\log_2(n)) = m + \log_2(\log_2(a))$$ Hence, $$m = \log_2(\log_2(n)) - \log_2(\log_2(a))$$ This gives us that $$T(n) = 2 \log_2(\log_2(n)) - 2\log_2(\log_2(a)) + T(a)$$ Hence, $$T(n) = \mathcal{O}(\log_2(\log_2(n)))$$