Why is $nlog(n)=\Theta(n^2)$ not true?

Question

I want to demonstrate this relation. I know that $f(n)=\Theta(g(n))$ when $\exists c_1>0, c_2>0, n_o\in \mathbb{N} \mid \forall n \geq n_0$ for which: $$c_1g(n) \leq f(n) \leq c_2g(n)$$ For the first part of the relation, I have $c_1n^2 \leq nlog_{10}(n)$. How can I now demostrate that these $c_1$ and $n$ exist (or better, don't exist, since I know that the initial equation is wrong)?

EDIT: Sorry, I forgot to say. I can't use logarithms, only the definition of $\Theta$

Answer 1

Well take $c_1\geq10^{-t}$ for some $t$ then you have that for $n=10^{2t}$ for example that $$c_110^{4t}\leq 10^{2t}2t\\2t\geq c_110^{2t}\geq10^t$$ But $2t< 10^t$ for any $t\geq1$ contradiction; hence there doesn't exist such $c_1$ since by assumption $t$ is arbitrary

Answer 2

A little example ,make a sense . $$n=100 \to nlogn=200 ,n^2=10^4\\n=10^5 \to nlogn=5\times 10^5 ,n^2=10^{10}$$ does it make a sense ?

Answer 3

$$\lim_{n\to\infty}\frac{n\log_{10}n}{n^2}=\lim_{n\to\infty}\frac{\log_{10} n}n=0$$

Then there exists some $N\in\Bbb N$ such that $n\log_{10} n<c_1n^2$ whenever $n\ge N$.

Answer 4

If you can use calculus, it is fairly simple. Suppose that there exist $c_1>0$ such that $c_1\le \frac{n\log_{10}(n)}{n^2}$ for all $n$ large enough. Take the limit: $$c_1\le \lim_{n\rightarrow \infty}\frac{n\log_{10}(n)}{n^2}=\lim_{n\rightarrow \infty}\frac{\log_{10}(n)}{n}=0$$ contradiction.

In other words you have proved that $n\log_{10}(n)=o(n^2)$, so $n\log_{10}(n)\ne\Theta(n^2)$