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

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}$$

• You seem to be confusing $\omega$ and $o$. May 21 '20 at 16:56
• Thanks Yuval, I made the changes May 21 '20 at 19:13

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$$

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).$$

• This answered my question because he explained the three different classifications from the limit function unlike the answer below. I prefer the second method because it seems to follow a more formal approach. Thanks. May 22 '20 at 19:51

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.$$

• I don't understand how that is a sufficient condition ? So we don't have to find witness pairs? May 21 '20 at 19:14
• Assume that $f(x)$ and $g(x)$ are two functions that are eventually positive. By definition of limit, $\lim_{x \to \infty} \frac{f(x)}{g(x)}$ is $+\infty$ if $\forall c\, \exists n_0 \, \forall n> n_0, \, \frac{f(x)}{g(x)} \ge c$. This implies that $\forall c>0 \, \exists n_0 \, \forall n> n_0, \, f(x) \ge c g(x)$, i.e., that $f(x) = \omega(g(x))$. In this way you have shown that, for all $c>0$, there must be some value of $n_0$ (that depends on $c$) that satisfies the definition of $\omega(\cdot)$ without bothering to explicitly compute such $n_0$. May 21 '20 at 19:23