Is $n^{\log \log n}$ polynomial, exponential or subexponential in $n$?
Is $n^{\log \log n}$ polynomial in $n$?
1
$\begingroup$
asymptotics
2 Answers
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.