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.

Say for example I say that:

$$ 2n^2 + n - 8 \quad\text{is}\quad O(n^3) $$

To prove this I must find a constant $c$ and a point $n_0$ for which $n^3$ is an upper bound of the equation.

This is easy to see because $n^3$ will always be larger than $2n^2$ (dominant term) for any constant $c$. How do I find $n_0$?

share|improve this question
1  
I don't understand the next to last sentence, there is no $c$ in "$n^3$ will always be larger than $2n^2$." You want to show that there is a constant $K$ such that (after a while) $2n^2+n-8$ is less than $Kn^3$. Note that for positive $n$, $2n^2 \le 2n^3$, $n \le n^3$, so $2n^2+n-8<3n^3$ for all positive $n$. –  André Nicolas Sep 28 '11 at 19:48
    
@André: you mean $n \ge 1$ - n positive assumes n integral, which is not stated. –  Mark Bennet Sep 28 '11 at 19:57
    
@Mark: It’s strongly implied by the use of $n$ (rather than $x$, for instance). –  Brian M. Scott Sep 28 '11 at 20:36
    
@Mark: The algorithms tag makes $n$ integral. –  Aryabhata Sep 28 '11 at 20:37
    
@Mark Bennet: Thanks, it would have been better to write $n \ge 1$. But one cannot edit. The main point was to remind the OP about the meaning of $O(n^3)$, since the reference to $c$ in the post is obscure, and might be the source of the uncertainty. –  André Nicolas Sep 28 '11 at 20:48

1 Answer 1

up vote 2 down vote accepted

The $-8$ makes the examples harder to see, so I will ignore it. As you say, you want to choose $c$ and $n_0$ so that $n \gt n_0 \implies cn^3 \gt 2n^2+n$. You get to choose $c$ and $n_0$ and there are many choices that will work. One choice would be $c=1$, in which case you can show that $n_0=2$ (or anything larger) will work. Also, you could choose $n_0=0,$ in which case $c$ needs to be at least $4$.

share|improve this answer
    
Ohhh, so once you've found a valid c, you simply sub in to find the value of n? –  maxmackie Sep 28 '11 at 21:54
    
Generally that works because the bounding function grows faster so once it gets bigger it stays bigger. But you could have cases where it falls below. For example, $cn^3$ vs $50n^2-100n$. You might choose $c=1$ and note that $2^3\gt 50\cdot 2^2-100\cdot 2$. But $3^3\not \gt 50\cdot 3^2-100\cdot 3$ –  Ross Millikan Sep 28 '11 at 22:10

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.