0
$\begingroup$

The question is:

Show that $$\log_2(n!)\in O(n \log_2(n)).$$

I'm guessing I'll have to use principle of simple induction for this one. But how would I go about writing the proof for this? Should I use proof by cases?

What will be my first assumption? Usually the other proofs I wrote, there was a domain assumption and I assume x in set of integers, etc. Not sure what to write for this one.

Thanks for your help!

$\endgroup$
2
$\begingroup$

$$0 \le \log n! = \log \prod\limits_{k=1}^n k = \sum\limits_{k=1}^n \log k\le \sum\limits_{k=1}^n \log n = n\log n$$

$\endgroup$
1
$\begingroup$

Since $n!$ is the product of $n$ factors, each of which is at most $n$, it follows that $\log_2(n!)$ is the sum of $n$ summands, each of which is at most $\log_2n$.

$\endgroup$
0
$\begingroup$

Using the fact that $\log ab= \log a +\log b$, it should be straightforward to show by induction that $\log n! < n \log n $ for $ n> 1 $.

$\endgroup$
0
$\begingroup$

Stirling's approximation says that $$n! \sim \left( {n\over e}\right)^n {1\over \sqrt{2\pi n}}.$$ What happens when you take $\log_2$ of this?

$\endgroup$
-1
$\begingroup$

First you should prove that $n!=O((n \ln n)^2).$ It implies $\ln n!=O(n \ln n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.