how to prove that nlogn is not Θ(n) without using limits?

i'm studying an algorithms designing and analysis , and i've question about Big-theta

how can i prove that nlogn is not Θ(n) without using limits ?

Remember that $f \in \Theta(g) \iff f \in O(g) \land g \in O(f)$, so $f \notin \Theta(g) \iff f \notin O(g) \lor g \notin O(f)$.

One definition of big-O notation that doesn't use limits is

$$
f \in O(g) \triangleq \exists c, N, \forall n > N, f(n) N \implies f(n) N) \lor f(n) N) \lor f(n) N) \lor f(n) N) \land \lnot (f(n) N, \lnot (f(n) N, f(n) \geq c \cdot g(n)\\
$$

So, to show that $n \log n \notin \Theta(n)$, you'll want to find a witness $n$ that will be based on a $c$ and $N$ that are abstract, and show that $n \log n \geq c \cdot n$.

Here is an example with some other functions:

Claim: $n^2 \notin O(n)$.

Proof:
Given $c$ and $N$ as above, let

$$n \triangleq \begin{cases}
c & N < 1\\
N c & N \geq 1.
\end{cases}$$

In the first case, $n^2 = c^2 \geq c \cdot c = c \cdot n$.

In the second, $n^2 = N^2 c^2 = N (N c^2) \geq N c^2 = c (c N) = c \cdot n$.

I won't do the example with $n \log n$, because I'd like you to see the principle and I don't want to accidentally do you homework.

StackExchange Computer Science Q#54063, answer score: 8