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

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?

• You want to prove that the relation $f(n)=\Theta(g(n))$ is false, so you have to prove that $c_1$ and $c_2$ don't exist. In your reasoning, if $c_1=1$, you have $n\le \log n$ that is an absurd. – Exodd Jan 10 '17 at 11:35
• @Exodd it's very similar to my idea. I worried about the fact that this could be not sufficient – Franco Scarpa Jan 10 '17 at 11:43
• well, in fact it isn't sufficient. You have to show that for every couple $(c_1,c_2)$ your inequalities don't hold. – Exodd Jan 10 '17 at 11:45
• @Exodd well, ok, but my question is exactly this! – Franco Scarpa Jan 10 '17 at 13:04

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$$
• I said in the description, I want only to use the definition, finding these $c_1$, $c_2$ and so on, without limits. I need a reasoning that lets me find those values. – Franco Scarpa Jan 11 '17 at 10:32