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?
No comments:
Post a Comment