What sequence is dominant between
$ f(n) = n!$ and
$ g(n) = 2^n$ or (or $a^n$)
I mean $ f/g -> 0 $ or $infinity$
What sequence is dominant between
$ f(n) = n!$ and
$ g(n) = 2^n$ or (or $a^n$)
I mean $ f/g -> 0 $ or $infinity$
Stirling's approximation states that:
$ \lim_{n \rightarrow \infty} {\frac{n!}{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^n}} = 1 $
Or:
$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n $
Which means that $n!$ grows faster that $a^n$. This is easy to see intuitively, given how $a^n$ consists of $n$ constant terms, whereas $n!$ consists of $n$ increasing terms. For large enough $n$, $n!$ will be larger.
The factorial grows faster because it consists of $n$ factors of increasing size, while the power $a^n$ consists of $n$ factors of constant size.