0
$\begingroup$

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.

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.