Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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}$
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).$
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. $$
