What is O(log(n!)), O(n!), and Stirling’s approximation?
O(n!) isn’t equivalent to O(n^n). It is asymptotically less than O(n^n). O(log(n!)) is equal to O(n log(n)). Here is one way to prove that: Note that by using the log rule log(mn) = log(m) + log(n) we can see that: log(n!) = log(n*(n-1)*…2*1) = log(n) + log(n-1) + … log(2) + log(1) Proof that O(log(n!)) … Read more