Show that x^2 is not Big O(x*log(x))?

Answer 1

It suffices to show that the limit as x approaches ∞ of (x^2) / (x * log x) is ∞. This will show that x^2 is asymptotically greater than x * log (x).

lim x->∞ (x^2) / (x * log x)
= lim x->∞ x / log (x)

Use L'Hospital's Rule:

lim x->∞ x / log (x)
= lim x->∞ 1 / (1/x)
= lim x->∞ (x)
= ∞.

So x^2 is not Big O(x * log (x)).

Answer 2

see my other answer about big O

x² / (x log(x)) is like x / logx and approaches infinity when x approaches infinity then x² /(xlogx) is not limited, and x² is not O[xlog(x)]