# Little-o proof by definition

I'm trying to figure out how to prove the following but to no avail.

Given the following functions :

$f(n) = n^3 -4n$

$g(n) = 5n^2 + 3n$

I have to show that $g(n) = o(f(n))$ by definition, that is not using limits or O definitions.

Notice that we say that $f(n)$ is $o(g(n))$ if for any real constant $\epsilon > 0$, there exists an integer constant $n_0 >= 1$ such that $f(n) < \epsilon g(n)$ for every integer $n>=n_0$.

I was trying to use some calculus techniques to solve it.

Here is what I have so far:

I'm looking for $n_0 >= 1$ such that $\epsilon_0 >= (5n^2+3n)/(n^3-4n)$ for every $n>= n_0$

Can someone explain me how can I continue from here? If I solve this inequality I believe It will give me the required $n_0$ for the $\epsilon$.

-

For every $\varepsilon\gt0$, choose $n_\varepsilon\geqslant4$ such that $n_\varepsilon\geqslant8/\varepsilon$. Then, for every $n\geqslant n_\varepsilon$, $$g(n)=5n^2+3n\leqslant8(n^2-4)=8f(n)/n\leqslant(8/n_\varepsilon)f(n)\leqslant\varepsilon f(n).$$ The only nontrivial step is the assertion that $5n^2+3n\leqslant8(n^2-4)$, but this is equivalent to the inequality $3n(n-1)\geqslant32$, which indeed holds for every $n\geqslant4$.

-
Can you please explain me how did you get to the nontrivial step. the assertion g(n) <= 8(n^2-4) and 8/n_epsilon – SyndicatorBBB Nov 4 '12 at 14:20
If $n\geqslant4$, then $3n(n-1)\geqslant3\cdot4\cdot3=36\geqslant32$ hence $3n^2\geqslant3n+32$ hence $8n^2-32\geqslant5n^2+3n$, QED. – Did Nov 4 '12 at 14:22
Okay I'll think about this but just how did you get from 8(fn)/n to (8/n_epsilon)*f(n) ? the last part – SyndicatorBBB Nov 4 '12 at 14:24
Oh I understand. You assumed epsilon is bigger than 8/n_epsilon, right? – SyndicatorBBB Nov 4 '12 at 14:26
The answer is easy: I started from $g(n)\leqslant\varepsilon f(n)$ and tried to massage this inequality until it was somehow related to $n\geqslant$some function of $\varepsilon$. Naturally, a second phase was then necessary, which was to check that the path could be reverted, that is, that $n\geqslant$something **implied** $g(n)\leqslant\varepsilon f(n)$ (since this is the implication one is interested in). – Did Nov 4 '12 at 15:21

Hint as $n$ tends to infinity

$$\frac{5n^2+3n}{n^3-4n} \sim\frac{5n^2}{n^3}=\frac{5}{n}$$

-
Just to make sure I understand. This limitation caluclation allows me to detemine that my n_0 is bigger than 5/n ? – SyndicatorBBB Nov 4 '12 at 12:30
@Guy: Limits never yield values of $n_0$. This is because one can modify as many terms of a sequence as one wants (but a finite number) without changing the limit. Hence, if you think some $n_0$ works, change the $100n_0$ first terms and your $n_0$ does not work anymore. :-) To get some $n_0$, one needs quantitative methods (and fortunately, these exist). – Did Nov 4 '12 at 14:27
Yes that's why I was so confused. Thank you for the clarfication. – SyndicatorBBB Nov 4 '12 at 14:54