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$
$\endgroup$
8
-
$\begingroup$ Welcome! Why are you interested in this recurrence? What have you tried? Have you checked our reference question? $\endgroup$– RaphaelCommented 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$– panthera oncaCommented 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$– RaphaelCommented 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$– panthera oncaCommented 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$– JeffECommented Aug 30, 2012 at 11:51
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
0
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).
