I need to find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$.I thought first to make a substitution: $m=\log n$. Then:$$T(2^m)=T(2^{m \over 2})+10\log m$$Let $S(m)=T(2^m)$:$$S(m)=S\big({m \over 2}\big)+10\log m$$Now we can use Master theorem. Suppose it's the case when $f(m)=O(m^{\log_2 1-\epsilon})=O(m^{0-\epsilon})$. Let $\epsilon=0.5$ then:$$\lim_{n\to \infty}\frac{10\log m}{m^{0.5}}=0$$Hence according to the Master theorem $T(m)=\Theta(m^0)=\Theta(1)$.Am I in the right direction?
Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$
asymptotics;recurrence relation;check my answer
We can expand the recursion (ignoring the constant 10) as follows:$$\begin{align*}T(n) &= \log \log n + \log \log n^{1/2} + \log \log n^{1/4} + \log \log n^{1/8} + \cdots \\ &=\log \log n + \log \frac{1}{2} \log n + \log \frac{1}{4} \log n + \log \frac{1}{8} \log n + \cdots \\ &=\log \log n + (\log \log n - \log 2) + (\log \log n - \log 4) + (\log \log n - \log 8) + \cdots\end{align*}$$At this point, let us notice that the number of terms is roughly the value of $k$ satisfying $n^{1/2^k} = \Theta(1)$, which translates to $\frac{\log n}{2^k} = \Theta(1)$ and so $\log n = \Theta(2^k)$, implying $k \approx \log_2 \log n = (\log \log n)/\log 2$. Keeping $k$ symbolic at first, we have$$\begin{align*}T(n) &= k \log\log n - (\log 2)(0 + 1 + 2 + 3 + \cdots + (k-1)) \\ &=k \log\log n - \frac{\log 2}{2} k(k-1) \\ &\approxk \left(\log\log n -\frac{\log 2}{2} k \right).\end{align*}$$Substituting our approximation for $k$, we deduce$$T(n) \approx \frac{\log \log n}{\log 2} \left(\log\log n - \frac{\log\log n}{2}\right) = \frac{(\log \log n)^2}{2\log 2}.$$In particular, $T(n) = \Theta((\log \log n)^2)$.