Proving a BIG-O statement? Logarithmic expressions. Simple Induction.

Question

I have to write a proof for the following statement.

$$\log_2(n!)\in\mathcal O(n\log_2(n))$$

What approach would you recommend. I am kind of LOST trying to figure this out.

I transformed the expression to logical symbols, I end up with this final expression.

$$\exists c\in\Bbb R,\exists\beta\in\Bbb N,\forall n\in\Bbb N,n\ge\beta\Rightarrow\log_2(n!)\le c(n\log_2(n))$$

I have to use the logarithmic rules and simple induction. But I have no idea how to assume the antecedent and determine de consequent for that exercise...

Answer 1

Hint: Show $n!\le n^n$ then use the rules for logs.

Answer 2

$\log_2(n!) = \dfrac{\ln(n!)}{\ln{2}}$

$n \log_2(n) = \dfrac{n\ln(n)}{\ln(2)}$

Using the formula from Stirling's approxmiation we have:

$\ln(n!) = n \ln(n) - n + O(\ln(n))$.

Substiuting the above formula in the first equation and taking a ratio of the first and second equations we have:

$H(n) = \dfrac{n \ln(n) - n + O(\ln(n))}{n \ln(n)} = 1 - \dfrac{1}{\ln(n)} + \dfrac{O(\ln(n))}{n\ln(n)}$.

The limit of $H(n)$ as $n \to \infty$ is 1, which indicates that

$\log_2(n!) \in \Theta(n \log_2(n)) \implies \log_2(n) \in O(n\log_2(n))$.