In a), you should say whether the following statements hold: log(n!) = O(nlog(n)), nlog(n) = O(log(n!)) and similarly with Θ and Ω replacing O.

Yes, but you can not only bound both functions fromaboveby nlog(n), you can also bound log(n!) frombelowby nlog(n), i.e., log(n!) = Θ(nlog(n)). This means that all six statements hold for these two functions.

Showing log(n!) ≤ nlog(n) is easy using properties of log. For log(n!) = Ω(nlog(n)) use a bound related to Stirling's approximation: .

For b), simplify both sides using the fact that ln(x) and e^x are mutually inverse.