Intereting Posts

Khan academy for abstract algebra
Property of abelian group
Show $\sum^\infty (2n-3)!!/(2n)!!$ converges
When the sum of independent Markov chains is a Markov chain?
Existence of Gergonne point, without Ceva theorem
splitting polygon in 4 equal parts
Where are the axioms?
Proof that 1-1 analytic functions have nonzero derivative
What are the limitations of the limit product rule?
How prove that polynomial has only real root.
How to represent XOR of two decimal Numbers with Arithmetic Operators
Proof of a simple property of real, constant functions.
Archimedean Property and Real Numbers
find examples of two series $\sum a_n$ and $\sum b_n$ both of which diverge but for which $\sum \min(a_n, b_n)$ converges
Show that if $n$ is any integer, then $\gcd(a+nb,b)=\gcd(a,b)$

In an example that I found, it is said that $\log(n!)$ has the same big-O complexity as $\log(n^n)$. Please explain why this is the case.

- Asymptotics of a double integral: $ \int_0^{\infty}du\int_0^{\infty}dv\, \frac{1}{(u+v)^2}\exp\left(-\frac{x}{u+v}\right)$
- Why is $\log(n!)$ $O(n\log n)$?
- Reformulation of Goldbach's Conjecture as optimization problem correct?
- Proof of Stirling's Formula using Trapezoid rule and Wallis Product
- Question about Big O notation for asymptotic behavior in convergent power series
- Behaviour of asymptotically equivalent functions after iterative exponentiation
- How fast does the function $\displaystyle f(x)=\lim_{\epsilon\to0}\int_\epsilon^{\infty} \dfrac{e^{xt}}{t^t} \, dt $ grow?
- Estimation of sums with number theory functions
- Meaning of “polynomially larger”
- Find asymptotics of $x(n)$, if $n = x^{x!}$

Because

$$\ln(n!) = \sum_{k=1}^{n} \ln(k) \leq n\ln(n) = \ln(n^n)$$

so $\ln(n!) = O(\ln(n^n))$

And for $n$ big enough,

$$\ln(n!) = \sum_{k=1}^{n} \ln(k) \geq \frac{n}{2} \ln\left(\frac{n}{2}\right) \geq \frac{n}{2}\left( \ln(n) – \ln(2) \right) \geq Cn\ln(n)$$

so $\ln(n^n) = O(\ln(n!))$

You have then

$$\ln(n^n) = \Theta(\ln(n!))$$

By writing

$$

\begin{align}

\log(n^n) – \log(n!) &= \log\left(\frac{n \cdot n \cdots n}{n \cdot (n-1) \cdots 1}\right) \\

&= \log\left(\prod_{k=1}^{n} \frac{n}{k} \right) \\

&= \sum_{k=1}^{n} \log\left(\frac{n}{k}\right) \\

&= n \sum_{k=1}^{n} \log\left(\frac{1}{k/n}\right)\frac{1}{n}

\end{align}

$$

and using the fact that the right-endpoint Riemann sum of a decreasing nonnegative function is a lower bound for the integral, i.e.

$$

0 \leq \sum_{k=1}^{n} \log\left(\frac{1}{k/n}\right)\frac{1}{n} \leq \int_0^1 \log\left(\frac{1}{x}\right)dx = 1,

$$

we obtain the estimate

$$

\log(n^n) – \log(n!) = O(n)

$$

or, rearranging,

$$

\log(n!) = \log(n^n) + O(n).

$$

Dividing through by $\log(n^n)$ yields

$$

\frac{\log(n!)}{\log(n^n)} = 1 + O\left(\frac{n}{\log(n^n)}\right) = 1 + O\left(\frac{1}{\log n}\right),

$$

so we can conclude that

$$

\lim_{n \to \infty} \frac{\log(n!)}{\log(n^n)} = 1.

$$

Stirling’s Formula is given by

$$n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1+O\left(\frac1n\right)\right)\tag 1$$

Therefore, we have from $(1)$ for $\log n!$

$$\begin{align}

\log\,n!&=\frac12 \log(2\pi)+\left(n+\frac12\right) \log n -n+O\left(\frac1n\right)\\\\

&=O\left(n\,\log n\right)\\\\

\end{align}$$

Since $\log n^n=n\log n$ we see immediately that

$$\log n! =O\left(n\,\log n\right)=O\left(\log n^n\right)$$

as was to be shown.

- Coloring 5 Largest Numbers in Each Row and Column Yields at Least 25 Double-Colored Numbers
- How to prove $f(\bigcap_{\alpha \in A}U_{\alpha}) \subseteq \bigcap_{\alpha \in A}f(U_{\alpha})$?
- If $(A-B)^2=O_2$ then $\det(A^2 – B^2)=(\det(A) – \det(B))^2$
- Why is $|e^{i \lambda z}| |e^{- \lambda y}|= |e^{- \lambda y}|$ here?
- Starting digits of $2^n$.
- Existence of iid random variables
- What is the inverse of the function $x \mapsto \frac{ax}{\sqrt{a^2 – |x|^2}}$?
- Compute $\int_0^\infty \frac{dx}{1+x^3}$
- A proof about polynomial division
- About an inequality including arithmetic mean, geometric mean and harmonic mean
- Prove $\bigcap \{A,B,C\} = (A \cap B) \cap C$
- Redundance of the Smoothness of the Inversion Map in the Definition of a Lie Group.
- Entropy of a binomial distribution
- How can I choose the best algorithm to integrate ODE's numerically?
- Horizontal and vertical tangent space of Orthogonal group