Why isn't $\log(n!) \leq O(n\log n)$?
I know that $\log(n!)$ is of $\Theta(n\log n)$ but why can't a function that is of $\Theta$ be $\leq$ than a function that is $O$ of the same parameter?
Isn't every function that is $\Theta(n\log n)$ actually lower or equals to $n\log n$ asymptotically (i.e., $O(n\log n)$)?
The big-O notation differs from the big-$\Theta$ notation in that $f(n)\in O(g(n))$ means that there is a function in $O(g(n))$ that bounds $f(n)$ from above, while $f(n)\in \Theta(g(n))$ means that there is a function in $\Theta(g(n))$ that bounds $f(n)$ from above and below.
In other words, in order for $\Theta(\log n!)\le O(n\log n)$ we must have constants $k_1,k_2,k_3$ and functions $g_1(n)\in \Theta(\log n!), g_2(n)\in O(n\log n)$ which satisfy $O(g_1(n))\le O(g_2(n))$ and
$$k_1\cdot g_1(n)\le \log n!\le k_2\cdot g_1(n)\\ |n\log n|\le k_3\cdot g_2(n)$$
Since we claimed that $O(g_1(n))\le O(g_2(n))$ (which can also be written $g_1(n)\in O(g_2(n))$ we must also have $k_4$ such that $|g_1(n)|\le k_4\cdot g_2(n)$.
There is no inherent contradiction produced by these claims.
EDIT:
By comparison (bringing in one of the later comments), the big-$\Omega$ notation describes functions that are bounded below by some function. So $f(n)\in \Omega(g(n))$ means there is a function $g_3(n)\in\Omega(g(n))$ and a constant $k_5$ such that
$$k_5\cdot g_3(n)\le f(n)$$
Now a contradiction is possible, but it does not appear that it has been presented yet.