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

Question

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.

Answer 1

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.$$

Answer 2

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$.

Answer 3

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.