Master's theorem applicability.

Question

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!

Answer 1

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)