Recurrence relation with O(loglogn)

Question

I am trying to solve a recurrence relationship as follows:

T(n)=T(n^1/2)+O(loglogn)

I can solve the T(n^1/2) part quite easily, but I am completely lost as to what to do with an O(loglogn). I cant use the masters theorem since loglogn cannot be expressed in the form of n^x and using trees, I don't believe I can just drop the O. Any guidance would be very helpful!

Thank you!

Edit: I did some more digging and found an advanced Master's Theorem and ended up getting T(n)=O(log^2(logn)). I am not sure how to derive the advanced Master's theorem from the standard one or how to solve the problem using trees/standard Master's theorem.

Answer 1

If $m:=\lg\lg n$, then $\lg\lg\sqrt n=m-1$. With $T(n)=T(2^{2^m})=:S(m)$, your recurrence becomes

$$S(m)=S(m-1)+O(m),$$ which has an $O(m^2)$ solution, and $$T(n)=O(\lg^2\lg n).$$

The result holds with logarithms in any base.

Answer 2

Hint: Let $U(k) = T(2^k)$. Find a recurrence relation for $U(n)$, solve it, and then infer a solution for $T(n)$.

Answer 3

Taking $\mathcal{T}\left(\cdot\right)=T\left(2^{(\cdot)}\right)$ and $z=\log_2 n$ we follow with

$$ \mathcal{T}\left(z\right)=\mathcal{T}\left(\frac z2\right)+O\left(\log_2 z\right) $$

and taking again $\mathbb{T}\left(\cdot\right)=\mathcal{T}\left(2^{(\cdot)}\right)$ and $u = \log_2 z$ we follow now with

$$ \mathbb{T}\left(u\right)=\mathbb{T}\left(u-1\right)+ O\left(u\right) $$

let $O\left(u\right) = k u$ then

$$ \mathbb{T}\left(u\right)=\mathbb{T}\left(u-1\right)+ k u $$

has the solution

$$ \mathbb{T}\left(u\right)=c_0 + \frac k2u(u+1) $$

and now going backwards with $u=\log_2 z$ and $z = \log_2 n$ we get

$$ T(n) = \frac k2\log_2(\log_2 n)\log_2(\log_2 n^2) $$

or

$$ T(n) = O\left(\log_2^2(\log_2 n)\right) $$