How to solve T(n)=2T(√n)+log n with the master theorem?

Question

I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?

Answer 1

Let us actually use the master theorem.

Define $S(n) = T(e^n)$ for all $n$. Then $$S(n) = T(e^n) = 2T(\sqrt{e^n}) + \log(e^n) = 2T(e^{n/2}) + n = 2S(n/2) + n$$ Now we can apply the second case of the master theorem to $S(n)$ for $a = b = 2$ and $f(n) = n$ to obtain $$ S(n) = \Theta(n\log n)$$ So for $n\gt0$, $$ T(n) = S(\log n) = \Theta(\log n \log\log n)$$

Answer 2

As discussed in the other answer, the Master Theorem does not apply here.

To solve this recurrence, we can follow the similar steps in Solving recurrence relation with square root.

For $n=2^m$, we have $$T(2^m)=2T(2^{m/2})+m.$$

Define $S(m)=T(2^m)$. Hence, we have:

$$S(m)=2S(m/2)+m.$$

Developping the recurrence (or you can apply the Master Theorem for $S(m)$), we obtain

$$\begin{align}S(m)&=2S(m/2)+m\\&=2(2S(m/4)+m/2)+m\\&=4S(m/4)+2m\\&=8S(m/8)+3m\\&\;\,\vdots\\&=2^{i}S(m/2^i)+im\end{align}$$

For $i=\log m$, we have:

$$\begin{align}S(m)&=mS(1)+m\log m\\&=mT(2)+m\log m\end{align},$$ or equivalently,

$$\begin{align}T(n)&=T(2)\log n+\log n \log\log n\end{align}$$

I think we can say that $$T(n)=O(\log n\log\log n).$$

Answer 3

The master theorem only applies to recurrences of the form $$T(n)=a\,T(n/b) + f(n)\,.$$ It says nothing about your recurrence. Our reference question on solving recurrences gives details of alternative techniques.

Answer 4

The Master Theorem states for $a \geq 1$, $b > 1$ and a function $f(b)$, let the recurrence relation be defined as follows \begin{equation} T(n) = aT(\frac{n}{b}) + f(n) \end{equation} We can distinguish three cases:\\ 1- If $f(n) = O(n^{\log_b(a-\epsilon)})$, for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.\ 2-If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.\ 3- If $f(n) = \Omega(n^{\log_b(a+\epsilon)})$, for some constant $\epsilon > 0$ and if $af(n/b) \leq cf(n)$, fpr some $c < 1$ and all sufficiently large $n$ then $T(n) = \Theta(f(n))$.\

You have $$T(n)=2T(\sqrt{n})+\log n$$ Do a change of variable $$n = e^m$$ So $$T(e^{2m}) = 2T(e^{m/2}) + m$$ Let $$G(m) = T(e^m)$$ Then $$G(2m) = 2G(m)+ m$$ or $$G(m) = 2G(\frac{m}{2})+ \frac{m}{2}$$ where $a = b = 2$ and $f(m) = \frac{m}{2}$. Since $f(m) = O(m) = O(m^{\log_2(2)})$, then we are at the second case, hence \begin{equation} G(m) = T(e^m) = \Theta(m^{\log_2(2)} \log m) = \Theta(m\log m) \end{equation} Now replace $m = \ln n$ since $n = e^m$, so \begin{equation} G(\ln n) = T(e^{\ln n}) = \Theta(\ln n\log \ln n) \end{equation} Hence \begin{equation} T(n) =\Theta(\ln n\log \ln n) \end{equation}

Answer 5

The above question could be solved using iterative method also.

\begin{align} T(n)=2T(n^{1/2})+\log(n)\label{eq1}\tag{1} \end{align} is given.

\begin{align} T(n^{1/2})=2T(n^{1/4})+\log(n^{1/2}).\label{eq2}\tag{2} \end{align}

By substituting $T(n^{1/2})$ in \eqref{eq1} we get

\begin{align} &T(n)=2(2T(n^{1/4})+\log(n^{1/2}))+\log(n),\\ &T(n)= 2\times2T(n^{1/4})+2\log(n^{1/2}) + \log(n). \end{align}

Here it is clear that $2\log(n^{1/2})=2\times1/2\times\log(n)=\log n$. Hence $T(n)$ becomes

\begin{align} 4T(n^{1/4})+\log(n)+ \log(n)= 2^2\times T(n^{1/4})+2\log(n)\label{eq3}\tag{3} \end{align}

Also by substituting $T(n^{1/4})$ in \eqref{eq3} we get

$$T(n)=2^3\times T(n^{1/8})+3\log(n).$$

Now on generalizing \eqref{eq3} we get

\begin{align} T(n)=2^k\times T(n^{1/2^k})+k\log(n).\label{eq4}\tag{4} \end{align}

Now assuming base condition as $T(1)=2$.

For base condition we need to substitute $(n^{1/2^k} = 2)$.

Applying $\log_2$ on both sides,

\begin{align} &(1/2^k)\times\log_2n = \log_2(2),\\ &\log_2n=2^k, \label{eq5}\tag{5}\\ &k=\log_2(\log_2n).\label{eq6}\tag{6}\\ \end{align}

Now substituting \eqref{eq5}, \eqref{eq6} in \eqref{eq4} we get,

$$T(n)=\log_2n\times T(1)+\log_2(\log_2n)\log n$$

where $T(1)=2$ by assumption.

Now we can say that $T(n)=O(\log n\log_2(\log_2n))$.