Big Oh notation involving $\log n!\in O(n\log n)$

272 Views Asked by At

I have worked hard on these questions and have found my own approach. I'm just checking if it makes logical sense for others and works. I'd appreciate any hints or better approaches.

Question 1: Prove that $\log n!\in O(n\log n)$

My Approach:

Assuming $\log n!\in O(n\log n)$

Then there must exist a case where there is a constant $c > 0$ and $k$ where $logn! < c ∗ nlogn$ for every $n > k$.

Consider when $c = 1$, then there should be a case where $logn! < 1 ∗ nlogn$ is true.

Suppose $k = 0$ then $logn!$ $ϵ$ $O(nlogn)$ since the inequality $logn! < 1 ∗ nlogn$ holds true for every case of $n > k$

1

There are 1 best solutions below

9
On BEST ANSWER

An example of a correct proof would be:

$$\log n!=\sum_{i=1}^n{\log i}\leq \sum_{i=1}^n{\log n}=n\log n$$

so $\log n!\in O(n\log n)$ since $\log n!\leq n\log n$ for all $n$.