how to 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 &gt; N, f(n) &lt; c \cdot g(n)
$$

The negation is logically equivalent to 

$$
\lnot (\exists c, N, \forall n,  n &gt; N \implies f(n) &lt; c \cdot g(n))\\
\lnot (\exists c, N, \forall n,  \lnot (n &gt; N) \lor f(n) &lt; c \cdot g(n))\\
\forall c, N, \lnot (\forall n,  \lnot (n &gt; N) \lor f(n) &lt; c \cdot g(n))\\
\forall c, N, \exists n, \lnot (\lnot (n &gt; N) \lor f(n) &lt; c \cdot g(n))\\
\forall c, N, \exists n, \lnot \lnot (n &gt; N) \land \lnot (f(n) &lt; c \cdot g(n))\\
\forall c, N, \exists n &gt; N, \lnot (f(n) &lt; c \cdot g(n))\\
\forall c, N, \exists n &gt; 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 &amp; N &lt; 1\\
N c &amp; 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.