3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – DanielV Feb 21 '15 at 1:42
  • 1
    $\begingroup$ @DanielV : I'm guessing $\lg$ is intended to mean $\log_2$. Do you disagree? ${}\qquad{}$ $\endgroup$ – Michael Hardy Feb 21 '15 at 2:07
  • $\begingroup$ @MichaelHardy It sure makes the question easier. But I think you should ask the poster. $\endgroup$ – DanielV Feb 21 '15 at 2:10
  • 1
    $\begingroup$ @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. $\endgroup$ – DanielV Feb 21 '15 at 17:25
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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