Mid exam

Question

Hi everyone!

I've been recently asked by one of my friends to prove an equation but still, I'm confused how to get it started tho.

log(n!) = Ω(nlog(n))

Does anyone know how to help?
I'll be very grateful if someone comes to reply to my issue.

Thanks in advance.

Comments

bro n! is just n^n

---

Thank you, brother.

Answer 1

n! can be written as n(n-1)(n-2).....1.

$n! = n(n-1)(n-2)...1.$

Highest order term in the product is $n^{n}$.

In time complexity , the lower order terms do not contribute.

Thus , $n! = \Omega(n^{n}) => log(n!) = \Omega(log(n^{n})) = \Omega(nlog(n))$

More formally , $log(n!) = \Theta(nlog(n))$

Comments

Thanks pal for your clear explanation, that helped me alot!
Finally, now I can understand this type of questions very easy and without any dark point remaining.