1
$\begingroup$

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

  • 0
    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)$....2012-04-05
  • 0
    @Hurkyl: I've made some changes , and would appreciate if you could check them out .2012-04-05
  • 0
    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$.2012-04-05
  • 0
    @Hurkyl : You mean that all the $define$S that I've made are not necessary ?2012-04-06
  • 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)2012-04-06

3 Answers 3

1

You are given that $$T(\sqrt{n})+A\log\log n\leqslant T(n)\leqslant T(\sqrt{n})+B\log\log n$$ for every $n$, for some constants $A$ and $B$. As in your post, let $$R(q)=T(2^{2^q})$$ then $$ R(q-1)+A\cdot(q\log 2+\log\log2)\leqslant R(q)\leqslant R(q-1)+A\cdot(q\log 2+\log\log2) $$ hence there exists $A'$ and $B'$ such that $$A'q\leqslant R(q)-R(q-1)\leqslant B'q$$ for every $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)}. $$

1

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

0

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

put $n=2^m$

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

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

assume $T(2^m) = S(m)$ then,

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

now put $m=2^r$

$S(2^r)=S({2^r}/2)+Θ(log(2^r))$

assume $S(2^r)=P(r)$

$P(r)=P(r-1)+Θ(r)$

$P(r)=P(r-2) ++Θ(r-1) +Θ(r)$

..

$P(r)=P(0) ++Θ(1)+Θ(2)... +Θ(r-1)+Θ(r)$

or

$P(r)=P(0)+Θ(r^2)$

putting back the value of r and m and getting relation in terms of T and n.

$T(n)=T(2) + Θ({(log(log(n))}^2)$

or

$T(n)=Θ({(log(log(n))}^2)$