How to prove n! is equivalent to $n^n$? I have been using $n!$ as $n^n$ when talking about big-$O$ and time complexity but never exactly knew why? I searched also but couldn't find anything. Somebody, please help me understand.
 A: $n!$ does not grow as fast as $n^n$ as $n\to \infty.$ 
Method 1:For integer $m\geq 1$ we have $\log m<\int_m^{m+1}\log x\;dx$ so for integer $n\geq 1$ we have $$\log (n!)=\sum_{m=1}^n\log m<\sum_{m=1}^n\int_m^{m+1}\log x \;dx=\int_1^{n+1}\log x \;dx=$$ $$=(n+1)\log (n+1) -n.$$ Subtracting $n\log n$  from this and re-arranging, we have $$\log (n!)-\log (n^n)<\log ((1+1/n)^n)-(n-\log (n+1))$$ and the RHS above goes to $-\infty$ as $n\to \infty.$
Method 2. (Simpler). For odd $n$ let $n'=(n+1)/2.$ For even $n$ let $n'=n/2.$ 
For  $n\geq 2$ we have $$n!=(\prod_{j=1}^{n'}j)\cdot (\prod_{j=n'+1}^nj)\leq (n')^{n'}\cdot n^{n-n'}.$$ So for $n\geq 2$ we have  $$n!/n^n\leq (n')^{n'}\cdot n^{n-n'}/n^n=(n'/n)^{n'}\leq \left(\frac {n+1}{2n}\right)^{n'}\leq \left(\frac {n+1}{2n}\right)^{(n/2)}\leq (3/4)^{(n/2)}$$
A: Actualy $n!=o(n^n)$
Here is a simple way to see this:
Let $a_n=\frac{n!}{n^n}$ then:

$$\frac{a_{n+1}}{a_n}=\frac{\frac{(n+1)!}{(n+1)^{n+1}}}{\frac{n!}{n^n}}=\frac{n^n(n+1)!}{n!(n+1)^{n+1}}=\frac{n^n}{(n+1)^n}=(\frac{n}{n+1})^n \to \frac{1}{e}<1$$

Thus from ratio test for sequences we have that $a_n \to 0$
A: It has already been answered that $$ \lim_{n\to\infty} \frac{n!}{n^{n}} = 0, $$
so using $n!$ as if it has the same asymptotic behavior of $n^{n}$ is not right. 
However, $ \log{(n!)} $ and $ \log{(n^{n})} $ are equivalent, as we can see by Stirling's approximation (see Stirling's approximation on Wikipedia):
$$  \sqrt{2\pi}\cdot \sqrt{n}\cdot n^{n}\cdot e^{-n} \leq n! \leq  e\cdot \sqrt{n}\cdot n^{n}\cdot e^{-n}  $$
$$ \Rightarrow n\log{(n)} -n+\log{(\sqrt{2\pi n})}  \leq \log{(n!)}  $$
Therefore, 
$$ \lim_{n\to \infty} \frac{n\log{(n)}+O(n)}{n\log{(n)}} = 1 =
\lim_{n\to \infty} \frac{\log{(n!)}}{\log{(n^{n})}} $$
I think it is worth pointing out because it is often used in computer science (the question mentioned time complexity) that $ \log{(n!)} $ and $ \log{(n^{n})} $ are equivalent, although $ n! $ and $ n^{n} $ are not, and that is a pretty counterintuitive idea, at least for me.
A: A crude but easy answer is that to compute $n!$, you are multiplying $n$ factors which are, on average, of order $n$.
More precisely, let's estimate $\log (n!)$ instead of $n!$. We have $\log n!=\log 1+\log2+\log3+\dotsb+\log n$. This expression looks like a Riemann sum for $\int\log x\,dx$. It could be the right-hand Riemann sum for $\int^n_0\log x\,dx$, which gives us the right upper bound, but is a divergent integral. Or it could be the left-hand Riemann sum for $\int^{n+1}_1\log x\,dx$, which is convergent, but has not the right upper bound we want (but would give a valid approximation for $n!$). Let's instead use the trapezoidal sum:
$$
\frac{1}{2}\log 1 + \log 2 + \log 3 + \dotsb + \log(n-1) + \frac{1}{2}\log n \approx \int^n_1\log x\,dx
$$
which has the right upper bound, and a lower bound that won't be divergent.
On the left-hand side of this approximation, we have 
$$\frac{1}{2}\log 1 + \log 2 + \log 3 + \dotsb + \log(n-1) + \frac{1}{2}\log n \\
= \log 1 + \log 2 + \log 3 + \dotsb + \log(n-1) + \log n - \left(\frac{1}{2}\log 1 + \frac{1}{2}\log n\right)\\
= \log(n!) - \left(\frac{1}{2}\log 1 + \frac{1}{2}\log n\right)
$$
And on the right-hand side, we have by using integration by parts
$$
\int^n_1\log x\,dx = (x\log x-x)\Big|^n_1 = n\log n -n + 1
$$
Putting it together, we have 
$$
\log(n!) \approx\left(\frac{1}{2}\log 1 + \frac{1}{2}\log n\right) + n\log n -n + 1\\
=(n+\frac{1}{2})\log n-n+1.
$$
Exponentiation gives
$$
n! \approx \frac{en^{n+\frac{1}{2}}}{e^n}=e\sqrt{n}\left(\frac{n}{e}\right)^n.
$$
So keeping only the leading order terms in each factor, we have that $\log(n!)$ is asymptotic to $n\log(n)$, which gives you the crude estimate $n!\approx n^n$ that you were looking for. 
Note that dropping sub-leading order terms yields an asymptotic expression for the logarithm, but this is no longer true after exponentiating, so the expression $n!\approx n^n$ should not be taken literally.
