# Recurrence relation with O(loglogn)

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.

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.

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

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)$$