3

an someone explain where did I do a mistake?

Solve the recurrence relation $$T(n)=2T(\sqrt{n})+\lg\lg n$$ Let$$\lg n = m$$ $$S(m) = 2S(m/2)+\lg m$$ We know (proved in class) that $$S(m) = O(m \lg m)$$ Therefore: $$T(n)= \Theta(\lg n \cdot \lg\lg n)$$

I will be thankful for you help!

RUstar
  • 33
  • I suggest being more precise and saying "Let $S(\lg n) = T(n)$" or "Let $S(n) = T(e^n)$", as let $\lg n = m$ is harder to really understand and reason about. – DanielV Feb 21 '15 at 01:42
  • 1
    @DanielV : I'm guessing $\lg$ is intended to mean $\log_2$. Do you disagree? ${}\qquad{}$ – Michael Hardy Feb 21 '15 at 02:07
  • @MichaelHardy It sure makes the question easier. But I think you should ask the poster. – DanielV Feb 21 '15 at 02:10
  • 1
    @RUstar I feel that I didn't address your question of where your answer went wrong, so I edited my response to try to clarify the divergence of the solutions. – DanielV Feb 21 '15 at 17:25

2 Answers2

3

This recurrence can be solved completely, which leads to insight as far as why the Theta asymptotic isn't correct.

$$T(n) = 2T(\sqrt n) + \lg \lg n$$

Similar to what you said , let $S(n) = T(2^n)$, so

$$S(n) = 2T(\sqrt{2^n}) + \lg \lg 2^n = 2T(2^{n/2}) + \lg n = 2S(n/2) + \lg n $$

Then do it again, let $R(n) = S(2^n)$:

$$\begin{align} R(n) &= 2S(2^n ~/~ 2) + \lg( 2^n ) \\ &= 2S(2^{n - 1}) + n \\ &= 2R(n - 1) + n \end{align}$$

which is a recursion that has a general solution

$$R(n) = 2^n\left(R(0) + 2\right) - 2 - n$$

Now we can back substitute using $S(n)= R(\lg n)$ to find that

$$S(n) = n\left(S(1) + 2\right) - 2 - \lg n$$

and again to find

$$T(n) = \lg n\left(T(2) + 2\right) - 2 - \lg \lg n$$

Now we can see that the asymptotic behavior is:

$$T \in \Theta\bigg(\lg n\bigg)$$

Can someone explain where did I do a mistake?

If the constants in the recursion had been different, then the $R(n)$ recursion could have had a $n2^n$ term in it: it would have been of the form

$$R(n) = Xn2^n + Y2^n + Zn + W$$

$X \ne 0$ would have added a $(\lg n)(\lg \lg n)$ term in the $T(n)$ solution.

$O()$ asymptotic is an upper bound , $\Theta()$ asymptotic is both an upper and lower bound.

So while it is true that $T \in O((\lg n)(\lg \lg n))$ as your attempt suggested, because of the choice of constants, the $(\lg n)(\lg \lg n)$ term disappears and the $(\lg n)$ term is left to uphold the the growth of $T$, being both an asymptotic upper and lower bound.

DanielV
  • 23,556
0

Your assumption that $$S(m)=2S(m/2)+\lg m$$ yields $$S(m)=O(m \lg m),$$ can be tightened. By the Master Theorem, $S(m) = \Theta(m)$.

See DanielV's answer for the full solution.

MarkG
  • 532