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


5 Answers 5


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


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:


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


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


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.

  • 1
    $\begingroup$ You might want to check my answer where I do use master theorem. $\endgroup$
    – John L.
    Aug 20, 2018 at 23:54
  • $\begingroup$ @Apass.Jack Sure, if you change variables to get a different recurrence. $\endgroup$ Aug 21, 2018 at 9:45

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}

  • $\begingroup$ OK but we already have two answers saying "change variables to $c^m$, solve that recurrence and substitute to get $T(n)=\Theta(\log n\log \log n)$. So what does your answer add? (And note that your form of the answer confusingly uses different bases in the logarithms: the suppressed constant factors in the big-Theta notation let you change all the bases to be the same.) $\endgroup$ Aug 21, 2018 at 9:49

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


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.