Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
Great explanation. –  peter_gent May 15 '13 at 20:27
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.