3
$\begingroup$

What sequence is dominant between

$ f(n) = n!$ and
$ g(n) = 2^n$ or (or $a^n$)

I mean $ f/g -> 0 $ or $infinity$

2 Answers 2

1

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.

2

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.

  • 0
    well I see your point n! is > a^n for n>a/2 right?2012-05-30