6
$\begingroup$

what is the complexity of below relation

$ T(n) = 2*T(\sqrt n) + \log n$

and $T(2) = 1$

Is it $\Theta (\log n * \log \log n)$ ?

$\endgroup$
8
  • $\begingroup$ Welcome! Why are you interested in this recurrence? What have you tried? Have you checked our reference question? $\endgroup$
    – Raphael
    Aug 29, 2012 at 12:19
  • $\begingroup$ @Raphael : I solved the recurrence but I was skeptical about the result. So posted the question here. I got this came across this eq while solving some recurrences. I got answer theta(log(n) * loglog(n)). $\endgroup$ Aug 29, 2012 at 13:00
  • 1
    $\begingroup$ In that case, please edit your attempt into the question! Why ask people to do all the calculations if all you want is somebody to check yours? (SE does not work too well for questions of this type, by the way.) $\endgroup$
    – Raphael
    Aug 29, 2012 at 13:03
  • $\begingroup$ @Raphael I posted this question in math with the answer but I didn't get any answers so I posted it here without answer. I thought nobody will answer my question if it's already solved. I even edited this in math and I got the answer afterwards. Next time will keep this in mind while posting :) $\endgroup$ Aug 29, 2012 at 13:08
  • 2
    $\begingroup$ Do you really want the complexity of the recurrence, or do you just want its solution? $\endgroup$
    – JeffE
    Aug 30, 2012 at 11:51

1 Answer 1

6
$\begingroup$

Yes, the answer is $\lg n \cdot \lg \lg n$:

Reason this out by expanding the recurrence and looking for a pattern:

\begin{align*} T(n) &= 2T(\sqrt{n}) + \lg n \\ &= 2( 2T( \sqrt[4]{n} ) + \log(\sqrt{n}) ) + \lg n \\ &= 2\left( 2T(\sqrt[4]{n}) + \frac{1}{2} \lg n \right) + \lg n \\ &= 4T( \sqrt[4]{n} ) + 2 \lg n \\ &= 4( 2T( \sqrt[8]{n} ) + \lg\sqrt[8]{n} ) + 2 \lg n \\ &= 8T( \sqrt[8]{n} ) + 3 \lg n \\ \end{align*} So as we continue expanding this and taking the square root of $n$, we will eventually bottom out where $n < 2$. To figure out how many times we can take the square root of $n$, consider $n = 2^{\lg n}$, and on each recursive call, $n$ will have its square root taken. Ending when $n < 2$ gives us: \begin{align*} 2^{\frac{\lg n}{2^k}} &= 2 \\ \frac{\lg n}{2^k} &= 1 \\ \lg n &= 2^k \\ k &= \lg \lg n \end{align*}

Giving a solution of $\lg n \lg \lg n$.

Alternatively, this can be solved via variable substitution and the Master Theorem. Substituting $m = \lg n$: \begin{align*} T(2^m) &= 2T(2^{m/2}) + m \\ S(m) &= 2S(m/2) + m \end{align*} At this point the Master Theorem applies, with $a=2$, $b=2$, and $f(m) = m$. Since $m^{\log_b a} = m^{\lg 2} = m$, resulting in $f(m) = m = \Theta(m^{\log_b a})$. Therefore case 2 of the Master Theorem applies, and the solution is $m \lg m$. Substituting $m = \lg n$ gives us $T(n) = \lg n \lg \lg n$.

Edit: fixed a typo (needed to write this to exceed the minimum number of characters).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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