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

  • $\begingroup$ Welcome! Why are you interested in this recurrence? What have you tried? Have you checked our reference question? $\endgroup$ – Raphael Aug 29 '12 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$ – panthera onca Aug 29 '12 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 '12 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$ – panthera onca Aug 29 '12 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 '12 at 11:51

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


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.