# 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) < c \cdot g(n)$$

The negation is logically equivalent to

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

There should be a $C$ such that $n\log(n)<Cn$, or $\log(n)<C$ for $n>N$. This is not possible as the logarithm function is unbounded. [If there was such a $C$, then $n<e^C$ ?!]