Note: We defined asymptotic notation for functions $f : \mathbb{N} \to \mathbb{N}$, but the same definitions work for real-valued functions $f : \mathbb{N}\to\mathbb{R}$.
Let $f, g : \mathbb{N}\to\mathbb{R}$ be two real-valued functions greater than 1.
(a) True or false: $n! = \mathcal{O}(n^n)$? Prove your answer. (Hint: use Stirling’s formula.)
Stirling’s formula: $n! \sim \left(\frac ne\right)^n \sqrt{2\pi n}$.
There are two ways to take down the problem:
Method 1: Stirling's formula
As suggested by the question, $n!=\mathcal O(\sqrt nn^ne^{-n})$. Because $e^n$ grows substantially faster than $\sqrt n$, we have $\sqrt ne^{-n}=\mathcal O(1)$., which indicates $n!=\mathcal O(n^n)$.
Method 2: Elementary comparison
If we were to expand $n!$ and $n^n$, we have
$$ n!=1\cdot2\cdot3\cdot4\cdots n $$
$$ n^n=n\cdot n\cdot n\cdot n\cdots n $$
By comparing each term, we conclude that $n^n>n!$ for sufficiently large $n$.