Growth of exponential functions according to the big O notation

Question

I'm preparing for an exam and trying to make some sense of the growth of the different exponential functions. I picked the trickiest functions for myself and tried to sort them according to the big O notation. Since it's hard to use L' Hospital's rule on exponential functions I at least want to get a feeling for the order of growth.

$$ n^2 = O(ln(n) ^ {ln(n)}) = O(n^{ln(n)}) = O(2^{\sqrt{n}})=O(2^{(n/2)}) = O(n ^{\sqrt(n)}) = O(n!) = O(n ^n) $$

I'm particularly unsure about the right place of fac(n). Can anyone verify if that is correct?

Answer 1

You swapped two functions. Notice that: $$n^{\sqrt{n}} = 2^{\sqrt{n} \log n } = o(2^{\frac{n}{2}})$$.

Once this is fixed, the factorial is in the correct order since very rough inequalities show that $$n! = n \cdot (n-1) \cdot \ldots \cdot 2 \ge \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n-1 \text{ times}} = 2^{n-1} = \omega(2^{\frac{n}{2}}),$$ and $$n = n \cdot (n-1) \cdot \ldots \cdot 2 \le \underbrace{n \cdot n \cdot \ldots \cdot n}_{n-1 \text{ times}} = n^{n-1} = o(n^n).$$

In general, from Stirling's approximation you know that $n! = \Theta( \sqrt{n} \cdot (n/e)^n )$.