Show that n^3 log n is Ω(n^3)

Question

I understand that in order to prove big Omega, we must pick values for c and n such that the property is satisfied, but which values would I know to pick? Is there a way to do this using the limit rule?

Answer 1

The definition of big omega notation is that $f=\Omega(g)$ if $$ \limsup_{x\to\infty}|f(x)/g(x)|>0. $$ This means that there exists some $y\in \mathbb R$ and some $c>0$ such that for all $x>y$, we must have $|f(x)|>c|g(x)|$.

In this case, $f(x)=x^3\log x$ and $g(x)=x^3$. Choose $y=e$ and $c=1$. Then the statement $f=\Omega(g)$ follows because for all $x>e$, we have $$ x^3\log x > x^3\log e= x^3. $$