0
$\begingroup$

I'm ordering functions by their asymptotic growth for an assignment and I have verified I have the correct order by using limits, but I'm trying to understand why $n^{log\ log\ n}$ is between $n^3$ and $2^n$. It seems like it should be closer to the order of $n^n$. Can anyone provide some insight on this.

$\endgroup$
2
$\begingroup$

It could help if you wrote $n^{\log\log n}$ as $2^{\log n\log\log n}$. Then it should be clear that $2^{\log n\log\log n} = o(2^n)$. The morale of this is that the base of an exponent doesn't count as much as the exponent itself.

$\endgroup$
1
$\begingroup$

First, $3 \in O(\log\log(n))$ so $n^3 \in O(n^{\log\log(n)})$ and after taking the log of both $2^n$ and $n^{\log\log(n)}$ we see that $\log(\log(n))\times \log(n) \in O(n\log(2)) = O(n)$

To help with the argument of why $\log(\log(n))\times \log(n) \in O(n\log(2)) = O(n)$ take: $$\lim\limits_{n\rightarrow\infty} \frac{\log(\log(n))\times \log(n)}{n}$$ and apply L'Hôpital's rule to get $$\lim\limits_{n\rightarrow\infty} \frac{1 + \log(\log(n))}{n} = \lim\limits_{n\rightarrow\infty} \frac{1}{n} + \lim\limits_{n\rightarrow\infty}\frac{\log(\log(n))}{n} = 0 + 0 = 0$$

$\endgroup$
  • 1
    $\begingroup$ Thanks. This makes sense from a upper/lower bound point of view. I accepted Yuval's answer because the $n^{log\ log\ n}=2^{log\ n\ log\ log\ n}$ identity really gave me a clear conceptual picture of what I was looking for. I would upvote your answer but I don't have the rep yet. $\endgroup$ – realgenob Apr 7 '14 at 4:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.