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 from above by nlog(n), you can also bound log(n!) from below by 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.
Hi,
I assume you know calculus. The following are very often useful:
Let and be non-negative functions. Assume
1. If then and so also and .
2. If L=0, then , but (and so
Both 1) and 2) are easy consequences of the definition of limit and the orders.
Example:
Recall and so
By approximating Riemann sums and the fact that ln is increasing,
With a little more argument, you can see that
; i.e.
So by 1),