Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

$S(m)=S(m/2)+\log(m)$

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 ?

Regards

EDIT:

$R(q-1)=R(q-2)+Θ(q-1)⟹R(q)=R(q-2)+Θ(q)+Θ(q-1)$

$R(q-2)=R(q-3)+Θ(q-2)⟹R(q)=R(q-3)+Θ(q)+Θ(q-1)+Θ(q-2)$

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

Thanks

share|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
1  
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
add comment

2 Answers 2

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|improve this answer
add comment

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

Or:

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

share|improve this answer
add comment

Your Answer

 
discard

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.