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

| cite | improve this answer | |
$\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).$$

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You might want to check my answer where I do use master theorem. $\endgroup$ – John L. 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}

| cite | improve this answer | |
$\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
0
$\begingroup$

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

| cite | improve this answer | |
New contributor
Ridham Karia is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

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.