0
$\begingroup$

How do I prove that $3n\log(n!) \in O(n^2\log n)$?

Based on simpler exercises I did, it involves finding $n_0$ and $c$ such that $t(n) \leq c * n^2$ if we wanted to prove that $t(n) \in O(n^2)$.

Now I try to apply this in the above situation we would like to find a $c$ that makes this $3n\log(n!) \leq c \times (n^2\log n) $ true.

I have no idea what to do to find $c$ and the $n!$ bothers me because I don't know what to do with it.

$\endgroup$
  • $\begingroup$ Could you take for granted that log(n!)~nlog(n),n->inf? $\endgroup$ – Boxonix Jan 12 at 17:37
  • $\begingroup$ Hint: Stirling's formula $\endgroup$ – M.P Jan 12 at 17:39
6
$\begingroup$

Notice that $n!=1\cdot 2\cdots n\le n^n$. Therefore, $\log(n!)\le n\log(n)$. From that, we can conclude that $$3n\log(n!)\le 3n^2\log(n)$$

| cite | improve this answer | |
$\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.