# Is it possible to prove from the definition of big $O$ that $5n^3+7n+1$ is $O(n^3)$?

Is it possible to prove from the definition of big O that $5n^3+7n+1$ is $O(n^3)$? Can this be generalised to any case where you have to (and what is the procedure for working it out?) I guess the main question is there a specific term for this kind of procedure?

from the workings I've been given in class given $T\le O(f(n))$ if $n=1$ then $5n^3+7n+1 = 5^3+7+1 (23)$. Although I'm not sure how that relates to proving the above.

Thanks,

P.L.G.

-
p.p.s sorry for the vagueness :). –  peter_gent May 14 '13 at 21:31
I tried to correct the mathematics typesetting in your question. Please let me know if I did it wrong. –  MJD May 14 '13 at 21:33
I think that's indeed correct. :) –  peter_gent May 14 '13 at 21:34

All you need show to prove $f(n) = O(g(n))$ is that for some $N$ and some $C$ that

$$|f(n)| < c|g(n)|\quad\text{for all}\quad n\ge N.$$ You need not be at all efficient about this. So, to show $5n^3+7n+1 = O(n^3)$, assume $n \ge N = 1$.

\begin{aligned} 5n^3+7n+1 &\le5n^3+7n^3 + 1\cdot n^3\\ &= 13n^3 \end{aligned}

You can reduce the constant $13$ to $5+\epsilon$ by taking $N$ large enough. For example, find $N$ such that $$7n + 1 < n^3\quad\text{for}\quad n > N.$$

-
Great explanation. –  peter_gent May 15 '13 at 20:27

Hint: You must show that there is some positive $M$ such that for all $n$ (of sufficiently large absolute value), you have $$|f(n)|\le M|n^3|.$$ Use properties of absolute value, and the fact that $|n^k|\ge |n|$ for all $k\ge1$ and all $n$.

-

Big O notation is fundamentally (sort of) a measure of growth rate. So the growth rate of a polynomial $f(x)$ is going to be bounded by its leading term. Since the coefficients on the leading term are constants, they are irrelevant to the growth rate, and thus removed.

Wikipedia has a good example of this, applied to $f(x)=6x^4-2x^3+5$, and goes through, step by step, the process used to derive this. I'm not going to post it here, but it's pretty straightforward. Conceptually, it's the above statement.

-