Is $n \log n$ = $O(n)$ and is $n log n$ = $\Omega(n)$

Question

Hey guys i have been asked the above 2 questions with an explanation as to why. I'm quite confused, i know that the time it takes for an $O(n \log n)$ algorithm to run grows faster then a linear $O(n)$ algorithm but not quite sure the answer to these as that is not what the question is asking. I'm fairly sure the first is false and $\Omega$ is true but i'm not quite sure how to explain it. (i don't think we need to do an exact proof)

Answer 1

Showing that $n\log n=O(n)$ is equivalent to showing that the limit

$$\limsup_{n\to\infty}\frac{n\log n}{n}=\limsup_{n\to\infty}{\log n}$$

is finite which is false. However, the claim that $n\log n=O(n^2)$ is true as

$$\limsup_{n\to\infty}\frac{n\log n}{n^2}=\limsup_{n\to\infty}\frac{\log n}{n}$$

is finite by one application of L'Hôpital's rule. You could also visualize this by

You are correct that $ n\log n = \Omega(n) $.

To prove this, you need to show that there exists a $c>0$ and $n_0$ such that $n\log n \ge cn$ for all $n \gt n_0 ~(n,n_0\in\mathbb N)$. Try $ c = 1 $ and consider $n\geq 2$.