0
$\begingroup$

This question already has an answer here:

How can I prove that $n \log_2(n) ∈ O(log(n!))$ is true?

We start by supposing that $f(n)< c g(n)$ is true,

which means that $n \log_2(n) > c \log(n!)$ for all $n>n_0$ and $c>0$.

$\endgroup$

marked as duplicate by Did, user91500, Claude Leibovici, Watson, Kamil Jarosz May 31 '16 at 13:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Not that it matters, but in $\log(n!)$, what is the base? And you will end up wanting to show that $n\log_2(n)$ is less than $c\log(n!)$ for sufficiently large $n$. $\endgroup$ – André Nicolas Apr 13 '16 at 18:49
  • $\begingroup$ There are a lot of related questions, but you could first start with the usual trick: $\log(n!) = \log \prod_{j=1}^n j = \sum_{j=1}^n \log j > \sum_{j=n/2}^n \log j > \sum_{j=n/2}^n \log \frac{n}{2} > \dots$... $\endgroup$ – Clement C. Apr 13 '16 at 18:54
  • $\begingroup$ Related: see math.stackexchange.com/questions/1489770/… and linked posts therein. $\endgroup$ – Clement C. Apr 13 '16 at 18:55
  • $\begingroup$ They don't specify a base for log (n!).. I suppose it is not important when calculating the big O $\endgroup$ – Natalie Apr 13 '16 at 19:37
  • $\begingroup$ Could you please explain me why do you make the transition from ∑ j=n/2 to n (log j) >∑ j=n/2 to n (log n/2) ? $\endgroup$ – Natalie Apr 13 '16 at 19:38