1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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

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}

$\endgroup$
  • $\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$ – David Richerby Aug 21 '18 at 9:49

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.