Solving recurrence $T(n) = 2T(n^{1/2}) + O(\log\log\log(n))$ I'm trying to solve the recurrence
$$T(n) = 2T(n^{1/2}) + O(\log\log\log(n))$$
but I don't know how to do it because of the $O(\log\log\log(n))$
I would appreciate if anyone can help me.
Thanks.
This is what I did:
$$T(n^{1/2^k})+ \sum_{j = 0}^{k - 1} O(\log\log\log(n^{1/2^j})$$
 A: You've forgotten the effect of the $2$ in $2T(\sqrt{n})$.
You should instead get $$ T(n) = 2^k T(n^{1/2^k}) + O\left(\sum_{j = 0}^{k-1} 2^{j} \log\log\log n^{1/2^j}\right)$$
Now, trivialising the $n^{1/2k}$ in the first term takes $k = \log\log n$ [1]. Then the first term clearly scales as $\log n$. The logs in the second have the following behaviour: $$ \log\log\log n^{1/{2^j}} = \log \log (\log(n)/2^j) = \log( \log\log n - j).$$ This tells us that us that the second term scales as $$ \sum_{j = 0}^{\log\log n -1} 2^j \log(\log\log n - j).$$
It should be easy to see that this term is going to dominate the complexity, since the $j = \log\log n - 2$ term in the sum is $\Omega(\log n).$ So, we need to get a handle on this sum.
For convenience, let me redefine this sum a function of a generic variable $m$ (which avoids having to type $\log\log$ all the time). Let $$ f(m) :=  \sum_{j = 0}^{m-1} 2^j \log (m-j),$$ which we shall proceed to upper bound. To this end, observe that the function $2^x \log(m-x)$ increases for $x \le m-3$ (the $-3$ isn't so important - it should however be evident that the function increases up to $j \le m - C$ for some $O(1)$ constant $C$). This means that $$ f(m) \le 2^{m-2} \log 2 + \int_{x = 0}^{m-3} 2^x \log(m-x) \mathrm{d}x \\
= \Theta(2^m) + 2^{m-3} \int_{y = 0}^{m-3} 2^{-y} \log(3 + y)\mathrm{d}y \\ \le \Theta(2^m) + \Theta(2^m) \int_{y = 0}^\infty 2^{-y}\log(3+y) \mathrm{d}y.$$ It should be straightforward to argue that the final integral above is bounded. So we end up with $f(m) = \Theta(2^m)$. This in turn means that $T(n) = O( f(\log\log n)) = O(\log n)$.

[1] To clarify this point, which came up in the comments: in the relation $T(n) = 2^k T(n^{1/2^k})) + \cdots,$ we have $T$ of some function of $n$ on both sides. To control $T$ itself, we need to reduce the $T(n^{1/2^k})$ on the right hand side to some value of $T$ upon which we already have control. Typically, it is assumed that for constant sized problems, $T$ is a constant. So, if we take $k$ so large that $n^{1/2^k} \le C$ (think of $C$ as just $1$ or $2$ if you like), then we'll have a $2^k T(C)$ bound, and now we can treat $T(C)$ as just a constant. This is what I mean by trivialising the $n^{1/2^k}$. In this particular case, to ensure that $n^{1/{2^k}} < 2,$ say, we need to take $k > \log\log n - \log\log 2$. For convenience, we can just set this to $\log\log n$ (or I guess ceiling or floor of that - it doesn't really matter, since asymptotics are usually not sensitive to such small perturbations).
