How to you prove that n*log n is in O(n)?

Question

I am working on Big-Oh, but I stuck on the proving part.

Question is to prove

n*log n is in O(n).

Given that there is a formula to check if it is in big-Oh I tried

F(n) <= c*g(n)

n*log n <= 1*n

Then I got log(n) <= 1 , where n>n0. So if I substitute 100 to n, the result is bigger than 1.

(I checked the answer the function is in O(n))

Answer 1

You can prove it is not in O(n) pretty easily.

Assume the claim is true, so by definition of big O:

There are constants N, c such that for all n > N > 0: n log n <= c*n

n log n <= c*n  since n > 0
log n <= c
n <= 2^c

But for n = max {2^c+1, N+1} - the above does not hold true. Thus the initial assumption is wrong, and there are no such constants.

If there are no such constants, by definition of big O notation, n log n is NOT in O(n).