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

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