# Proving Little-Oh notation by definition

I need to prove by definition (show that for every $C$ there exists a $n_0$) that: $$5n^2+3n= o(n^3-4n)$$

By trying to simplify the expression I get to the point where I should prove that: $$\frac{5n^2+3n}{n^3-4n} < C$$.

Now, showing that $\lim\limits_{x\to\infty} \frac{5n^2+3n}{n^3-4n} = 0$ isn't a tough mission, but how do I prove it by definition? How do I point out specific $n_0$ for every $C$ that comes up? I'm asked to provide a tight answer and not let $n_0 = C^C$ so that the $n_0$ for sure will be large enough but to point out $n_0$ that is reasonably small.

Either you do what David suggested, or you do something like this:

Let $c > 0$. Then

\begin{align} 5n^2 +3n &\le c(n^3-4n) &\iff \\ 5n+3 &\le cn^2-4c &\iff \\ 0 &\le cn^2-5n-(3+4c) \end{align}

Now solve for $n$ and let $n_0$ be the bigger root of that term.

• After finding the root, what is the method of proving that that root actually works for every $n$ that is bigger or equals to that root? – Eran Oct 28 '13 at 15:52
• @Quaker: monotonicity. – G. Bach Oct 28 '13 at 16:06
• Could you please explain a little deeper? The square root of the following function is $\frac{5+\sqrt{16c^2+12c+25}}{2c}$, how can I substitute $n$ with this expression? – Eran Oct 28 '13 at 16:16
• @Quaker The function $f$ defined by the term $f(n) = cn^2 -5n -(3+4c)$ is monotonously increasing after its larger root for any $c>0$ as can for example be shown analytically by using the derivative (we don't have to worry about differentiability since we can just consider $f$ to be defined on $\mathbb{R}$, get the result there and then restrict its domain to $\mathbb{N}$). – G. Bach Oct 28 '13 at 16:21
• @Quaker Yes, it will; if you'd like to picture it, the graph of that term is a parabola that opens up. – G. Bach Oct 28 '13 at 16:26

You don't have to prove every single step by definition. So, prove that the limit is zero and then use the definition of "the limit as $x$ goes to infinity is zero" to show that the definition of $o(-)$ is satisfied.