0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ You seem to be confusing $\omega$ and $o$. $\endgroup$ May 21, 2020 at 16:56
  • $\begingroup$ Thanks Yuval, I made the changes $\endgroup$ May 21, 2020 at 19:13

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ May 22, 2020 at 19:51
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I don't understand how that is a sufficient condition ? So we don't have to find witness pairs? $\endgroup$ May 21, 2020 at 19:14
  • $\begingroup$ 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$. $\endgroup$
    – Steven
    May 21, 2020 at 19:23
  • $\begingroup$ See also this answer. $\endgroup$
    – Steven
    May 21, 2020 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.