0
$\begingroup$

I have to find out if the following recurrence can be solved with the master theorem:

$$T(n) = 3T\left(\frac{n}{2}\right) + n^{\log\log n}$$

I have figured that, here, I have the third case because $f(n) > n^{\log_2 3}$ but it understand that, in order for master to be applicable, $f(n)$ must be polynomially larger than $n^{\log_23}$ and I have no idea how to verify it.

Any help would be much appreciated!

$\endgroup$
0
$\begingroup$

The third case asks for (here, $a=3,b=2$)

  • $f(n) = \Omega(n^{\log_2 3+\epsilon})$ for some $\epsilon > 0$
  • $3f(\frac{n}{2})\leq \kappa f(n)$ for some $\kappa < 1$ (and any $n$ large enough)

Observe than $f(n) = n^{\log \log n} = 2^{\log n\cdot \log \log n}$; $f$ is not polynomial, it's asymptotically greater than any polynomial (in particular, for $\epsilon=1$, $n^{\log_2 3+1} = 2^{\log n\cdot(\log_2 3+1)} = o(2^{\log n\cdot \log \log n})$. The first condition holds.

The second too, as \begin{align*} \frac{3f\left(\frac{n}{2}\right)}{f(n)} &= 3\cdot 2^{\log(\frac{n}{2})\cdot \log \log( \frac{n}{2}) - \log n\cdot\log\log n} = 3\cdot 2^{\log(n)\cdot \log \log( \frac{n}{2}) - \log \log( \frac{n}{2}) - \log n\cdot\log\log n} \\ &=3\cdot 2^{\log(n)\cdot \left(\log \log( \frac{n}{2}) - \log\log n \right)- \log \log( \frac{n}{2})} = 3\cdot 2^{\log(n)\cdot \left(\log \left( 1-\frac{1}{\log n} \right) \right)- \log \log( \frac{n}{2})} \\ &= 3\cdot 2^{\log(n)\cdot \left(-\frac{1}{\log n}+o(\frac{1}{\log n}) \right)- \log \log( \frac{n}{2})} = 3\cdot 2^{-1- \log \log( \frac{n}{2}) + o(1)}\\ &= \frac{3}{2}\cdot \frac{1}{\log\frac{n}{2}}\cdot 2^{o(1)} \xrightarrow[n\to\infty]{}0 \end{align*}

(you can also get a sanity check to see this limit is indeed $0$ with Mathematica, although it is not a proof)

$\endgroup$
3
  • $\begingroup$ I still didnt understand how did you demonstrate that the first condition holds, could you elaborate? $\endgroup$
    – Fireeyes
    Jan 28 '14 at 17:36
  • $\begingroup$ Look at the exponent: one of them is $C\log n$ (for the constant $C=\log_2 3 +1$, the other one is $\log n \cdot \log\log n$ (where $\log\log n \to \infty$, so clearly greater than $C$ for $n$ sufficiently large). $\endgroup$
    – Clement C.
    Jan 28 '14 at 17:50
  • $\begingroup$ I see now, it was actually very obvious. $\endgroup$
    – Fireeyes
    Jan 29 '14 at 3:39

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.