How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $

Question

I am trying to answer this question: $3x^3 +2x + 1$ is $ \omega(x \cdot \log x)$

My question is how to solve this question.

Here is what I have tried so far:

I applied the definition $3x^3 + 2x + 1 > c \cdot x\log x$ for all c, given $n \geq k$, for some k

I tried to apply the technique of applying the equality that: $n < n^3$

Since n is less than the highest order term we can just move all terms to order n ??

Giving $6x < c \cdot x \log x$

Then you can choose: $k < 2^\frac{6}{c}$

Answer 1

What I recommend first is to notice that if you're looking at the complexity of the function $3x^2+2x+1$, really all you should care about is the function $x^2$. because if you will prove that $x^2 = \omega(xlogx)$ then adding the $2x + 1$ won't ruin that proof since $x^2$ is polynomially bigger than $2x + 1$ and so we can just look at the $x^2$.

(I will use $n$ instead of $x$ because that is what I'm familiar with but it's exactly the same for $x$)

So now what we want to prove is that $$n^2 = \omega(nlogn)$$

which as you offered only you need to flip your sides in the equation, we will need to find a positive $C$, so that for any $n>n_0$ or $n>k$ : $$f(n)\ge C\cdot g(n)$$ when $f(n) = n^2$ , $g(n) = nlogn$

That will get us to: $n^2 \ge Cnlogn $

We can divide both side by $n$: $$n \ge Clogn$$

Now that's a bit of a tricky one. but "it is known" that polynomial running time is SLOWER than logarithmic one.

Basically what that means is that you'd prefer to reach a logarithmic complexity running time if possible because than you'll get faster execution.

Generally this is the order of running times when the first is the fastest:

$$1.Constant$$ $$2.Logarithmic$$ $$3.Linear$$ $$4.Linearithmic$$ $$5.Polynomial$$ $$6.Exponential$$

(you can read more about it here: https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course/)

Another way to see it is if you'll find the limit of the division of the two functions, let's say we'll choose: $${f(n) \over g(n)}$$

If $$\lim_{n\to \infty} {f(n) \over g(n)} \rightarrow \infty$$ It means that $f(n)$ is "much bigger" than $g(n)$

If $$\lim_{n\to \infty} {f(n) \over g(n)} \rightarrow 0$$ It means that $f(n)$ is "much smaller" than $g(n)$

The last option (Atleast in this method) is: $$\lim_{n\to \infty} {f(n) \over g(n)} \rightarrow C$$ When $C \gt 0$ which means both of the functions have Asymptotically the same complexity.

Back to our functions, we can see that : $$\lim_{n\to \infty} {n \over log(n)}$$

We will use lupital rule and get: $$\lim_{n\to \infty} {1 \over 1/n} \rightarrow \infty$$

We now can see that $f(n) = n$ is bigger Asymptotically from $g(n) = log(n)$ hence : $$n = \omega (log(n))$$

---

I really hope I explained as clear and easy as possible, it's just English isn't my mother tongue language so I apolegize in advance for any mistakes with grammer etc.

---

Update : I've noticed you've made changes to the original function and now it is $3x^3+2x+1$, yet the proof will be the same, just use $n^3$ and than you'll still get the same result when using lupital. That because, inevitably, if we just proved that $n^2$ is much bigger than $log(n)$ than of course that $n^3$ which is much bigger than $n^2$ would also be bigger than $log(n).$

Answer 2

The easiest way is to check that $\lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = +\infty$, which is a sufficient condition for $3x^3 + 2x +1 \in \omega(x \log x)$.

$$ \lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = \lim_{x \to \infty} \frac{3x^3}{ x \log x} = \lim_{x \to \infty} \frac{3x^2}{ \log x} = \lim_{x \to \infty} 6x^2 = +\infty. $$