How to prove $\omega$ bound without using limit?

Question

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.

Answer 1

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.

Answer 2

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!