1
$\begingroup$

How to show $n^{3.4} - 2015n^{2} + 3$ $\in$ $\omega(n^{3})$ without using limit?

According to the definition of $\omega$, $f(n)$ $\in$ $\omega(g(n))$ if and only if $\forall c > 0$, $\exists n_0$ such that $\forall n \geq n_0$, $f(n) \geq cg(n)$.

My thought is that I should look for a $n_0$ to satisfy the above definition, so I start with

$$n^{3.4} - 2015n^{2} + 3 \geq cn^3$$

However I have no idea how to simplify this inequalities, I try to divide both sides by $n^3$ but it seems get more complicated.

Can someone show me how to prove it or push me in the right direction? Any help will be greatly appreciated.

$\endgroup$
0
$\begingroup$

As you noticed by dividing by $n^3$, it is the same to show that $f(n) := n^{0.4} - 2015 n^{-1} + 3 n^{-3} \in \omega(1)$.

To do this, let's choose $N_1$ large enough that the second term is less than $1$ in magnitude; for this purpose $N_1:=2015$ is sufficient. So for $n \geq N_1$ we're considering a function which is larger than $n^{0.4} - 1$. We now need to show that this function can be made larger than any given constant $c$. But this inequality is easy to solve:

$$n^{0.4} - 1 \geq c \Leftrightarrow n \geq (c+1)^{1/0.4}.$$

So define $N_2 = \lceil (c+1)^{1/0.4} \rceil.$ If $n \geq N_2$ then $n^{0.4} - 1 \geq c$. At the same time, if $n \geq N_1$ then $f(n) \geq n^{0.4} - 1$. So if $n \geq \max \{ N_1,N_2 \}$, we have the desired inequality. So we can choose that to be our $N$ for the argument.

$\endgroup$
0
$\begingroup$

We are given $c$, which can be considered fixed from now on. Note that $$n^{3.4}-2015n^2+3\gt n^{3/4}-2015n^3.$$ So if $n^{3.4}-2015\ge cn^3$, then our desired inequality will be satisfied.

So if $n^{3.4}\ge (2015+c)n^3$, then our inequality will be satisfied. Equivalently, for $n\ne 0$, if $n^{0.4}\ge 2015+c$, then our inequality will be satisfied.

Certainly if $n$ is large enough, then $n^{0.4}\ge 2015+c$.

Remark: The limit argument is easier!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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