0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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 )$.

$\endgroup$
2
  • $\begingroup$ Thanks for the explanation. So I swap '2^(n/2)' and 'n^(sqrt(n))' and the order is right? $\endgroup$ – Paul Erlenmeyer Mar 30 '20 at 17:24
  • $\begingroup$ That's correct. $\endgroup$ – Steven Mar 30 '20 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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