How can I show that $nlog(n) \neq \Theta(n^2)$?

Question

I want to demonstrate this relation. I know that $nlog(n)=O(n^2)$, but I would like to prove the mistake of the relation in the title using only the definition of $\Theta$. By definition, $f(n)=\Theta(g(n))$ when $$\exists c_1, c_2>0, \exists n_0 \in \mathbb{N} \mid \forall n \geq n_0 \Rightarrow c_1g(n) \leq f(n) \leq c_2g(n)$$ I don't want to use limits to verify this, only this definition. So, I need to find two constants $c_1$ and $c_2$ that satisfy the relation. In my case, I have to prove that: $$c_1n^2 \leq nlog(n) \leq c_2n^2$$ I divide the three members for $n$: $$c_1n \leq log(n) \leq c_2n$$ At this point, I would end saying that I can simply take $c_1=c_2=1$ to verify the first and second part, since I know that $n = O(log(n))$. Am I wrong? Is it enough?

Answer 1

To disprove $n\log(n) = \Theta(n^2)$ you have to show

$$ \forall c_1, c_2>0, \forall n_0 \in \mathbb{N}, \exists n \geq n_0 \mid c_1n > \log(n)\, \vee \, \log(n) > c_2n $$ The second, in particular is false since $$ \lim_{n\to \infty} \frac{\log(n)}{n} =0 $$