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!
$$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$$
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$.
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 $.
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?
First you should prove that $n!=O((n \ln n)^2).$ It implies $\ln n!=O(n \ln n)$.
