1
$\begingroup$

Is $n^{\log \log n}$ polynomial, exponential or subexponential in $n$?

2 Answers 2

3

Not polynomial in $n$. For let $K$ be a (say large) constant. We show that ultimately $n^{\log\log n}\gt n^K$. We can do this by taking the $\log$ of both sides. On the left, we get $(\log n)(\log\log n)$. On the right, we get $K\log n$.

If $n$ is large enough, $\log\log n\gt K$. But $\log\log n$ grows glacially slowly, so we don't miss polynomialness by much. The behaviour is often called sub-exponential. For any $\epsilon \gt 0$, in the long run $n^{\log\log n}$ grows more slowly than $e^{n^\epsilon}$.

0

Well, taking the logarithm gives $\log \log n \cdot \log n$. This is sub-polynomial, so $n^{\log \log n}$ is sub-exponential.