So I am trying to disprove the claim that xlogx∈Θ(x2). Now, for some function f to be Θ of a function g, f∈Θ(g), means that f∈O(g)∧f∈Ω(g). Now it is intuitive that xlogx∈O(x2) but xlogx cannot be Big-Omega of x2 and, hence, I am trying to prove that xlogx∉Ω(x2) by proving the negation of xlogx∈Ω(x2).
Now, according to the definition of Big-Omega, if xlogx∈Ω(x2), then ∃c,x0∈R+,∀x∈N,x≥x0⇒xlogx≥c⋅x2.
Negating this and trying to prove it, we have; ∀c,x0∈R+,∃x∈N,x≥x0∧xlogx<c⋅x2.
Letting c,x0 be positive real numbers, I assume x≥x0. This automatically fulfills the first part of the and statement. How do I proceed from here to prove xlogx<c⋅x2? 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