# Helping prove this notation for Big-O(n!) Hello, I was wondering if anyone can help me prove the right part of this double equation. I know the left one is possible due tolog(n!) = Θ(nlogn). Any help is much appreciated.

• I don't get how you find the middle step from the left one. I mean it is true, but I don't get what calculation lead to having this exponent 5 inside the log. In any case $\log((n!)^5n^{10}) = 10\log(n) + 5\sum_{i=1}^n\log(i) = \Theta(n\log(n)) = \Omega(n) = \Omega(n^{2/3})$. (And as usual with these Landau notations, equality is not to be interpreted as a real equality, but more as membership/subset relationships) – Tassle Aug 29 '19 at 21:20
• @Tassle $\log((n!)^5n^{10})=5\log(n!)+10\log n=\Theta(n\log n + \log n) = \Theta(n\log n)=\Theta(25n\log n)=\Theta(5n\log n^5)$. Though I'm not sure why they didn't stop at $\Theta(n\log n)$. – David Richerby Aug 30 '19 at 10:47
• Oh yes I know how to establish these "equalities" of course (that's why I said "it is true"), but what I was wondering about is what would lead you to write this in the first place, what "natural" calcultion leads to this constant appearing (other than just arbitrarily multiplying by some constant). – Tassle Aug 30 '19 at 12:14

Remember that $$\Theta(5n \log n^5) = \Theta(n \log n)$$, since constant factors don't matter.
Then $$\Theta(n \log n) = \Omega(n \log n)$$, by the definition of big theta.
$$\Omega(n \log n) = \Omega(n)$$, because log is monotonic increasing (so we can remove it and still have a valid lower bound).
Finally, $$\Omega(n) = \Omega(n^{2/3})$$, by the properties of power functions.