Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need to find the bounds of the above recurrence .

I've tried the following however got stuck :

$T(n)=T(\sqrt{n})+Θ(\log(\log(n) )=$

$n=2^m,\quad m=\log(n)$

$T(2^m)=T(\sqrt{2}^m )+Θ(\log(log(2^{m})))=T(2^{m/2}) )+Θ(\log(m))$

Now define: $S(m)=T(2^m)$ then:


Now define : $q=\log(m)$ , $m=2^q$

And we get :$S(2^q)=S(2^q/2)+Θ(q)$

And finally , define : $R(q)=S(2^q )\Longrightarrow R(q)=R(q-1)+Θ(q)$

But how can I continue from here ?





What am I suppose to do with all the : $Θ(q)+Θ(q-1)+Θ(q-2)$ ?


share|cite|improve this question
You really shouldn't forget the constant in the big-$O$ notation. The recurrence $R$ you derive is one of the simplest recurrences: I bet you actually have it memorized, but didn't think to think about it! If you really can't see it, try writing out the first few terms explicitly in terms of $R(0)$.... – Hurkyl Apr 5 '12 at 21:21
@Hurkyl: I've made some changes , and would appreciate if you could check them out . – ron Apr 5 '12 at 21:55
While your work is no longer wrong, you've taken a step backwards. You can't do anything with $\Theta(q) + \Theta(q-1) + \cdots$, because any strange thing could be happening with the constants hidden in the big-$\Theta$ notation. You have to take advantage of the fact it all originated with the original $\Theta(\log \log n)$. I.E. that you know there are M and N so that $T(\sqrt{n}) + M \log \log n \leq T(n) \leq T(\sqrt{n}) + N \log \log N$. – Hurkyl Apr 5 '12 at 23:59
@Hurkyl : You mean that all the $define$S that I've made are not necessary ? – ron Apr 6 '12 at 0:07
No, you have the right underlying idea. See Didier's answer where he finished up the proof, rather than suggesting how you might see it for yourself. (The main thing I was hoping you'd notice is that you'd recognize $C q + C (q-1) + C (q-2) + \cdots$ as being a sum of consecutive integers) – Hurkyl Apr 6 '12 at 0:49
up vote 1 down vote accepted

You know that $T(\sqrt{n})+A\log\log n\leqslant T(n)\leqslant T(\sqrt{n})+B\log\log n$ for some constants $A$ and $B$. As in your post, let $R(q)=T(2^{2^q})$, then $$ R(q-1)+A(q\log 2+\log\log2)\leqslant R(q)\leqslant R(q-1)+A(q\log 2+\log\log2), $$ hence there exists $A'$ and $B'$ such that $A'q\leqslant R(q)-R(q-1)\leqslant B'q$. Summing this from $1$ to $q$, one gets $$ \frac{A'}2q^2\leqslant A'\sum_{k=1}^qk\leqslant R(q)-R(0)\leqslant B'\sum_{k=1}^qk\leqslant B'q^2. $$ Finally, $$ \color{red}{T(n)=\Theta((\log\log n)^2)}. $$

share|cite|improve this answer

After you get $S(m) = S(m/2) + \log(m)$, you can use the Master Theorem:

$f(m) = \log m = \Theta(m^{\log_2 1}\times (\log m)^1) = \Theta(\log m)$. Therefore

$$S(m) = \Theta(m^{\log_2 1}\times (\log m)^2)=\Theta((\log m)^2)$$


$$T(n) = \Theta((\log \log n)^2)$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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