# disproving $x \log{x} \in \Theta(x^2)$

So I am trying to disprove the claim that $$x \log{x} \in \Theta(x^2)$$. Now, for some function $$f$$ to be $$\Theta$$ of a function $$g$$, $$f \in \Theta(g)$$, means that $$f \in \mathcal{O}(g) \wedge f \in \Omega(g)$$. Now it is intuitive that $$x \log{x} \in \mathcal{O}(x^2)$$ but $$x \log{x}$$ cannot be Big-Omega of $$x^2$$ and, hence, I am trying to prove that $$x \log{x} \notin \Omega(x^2)$$ by proving the negation of $$x \log{x} \in \Omega(x^2)$$.

Now, according to the definition of Big-Omega, if $$x \log{x} \in \Omega(x^2)$$, then $$\exists c, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, x \geq x_0 \Rightarrow x \log{x} \geq c \cdot x^2$$.

Negating this and trying to prove it, we have; $$\forall c, x_0 \in \mathbb{R^+}, \exists x \in \mathbb{N}, x \geq x_0 \wedge x \log{x} < c \cdot x^2$$.

Letting $$c, x_0$$ be positive real numbers, I assume $$x \geq x_0$$. This automatically fulfills the first part of the and statement. How do I proceed from here to prove $$x \log{x} < c \cdot x^2$$? Even though it looks intuitive, I am think I am missing something. Is my proof headed in the right direction?

• Remember that $\log x = o(x)$. Jul 14, 2019 at 0:45

Suppose, if possible, $$x\log\, x\in \Omega(x^{2})$$ which means $$x\log\, x \geq cx^{2}$$ for $$x \geq x_0$$. Then $$\frac {\log \, x} x \geq c$$ for for $$x \geq x_0$$. Take limit as $$x \to \infty$$ and apply L'Hopital's Rule to get the contradiction $$0 \geq c$$.