# Algorithm analysis, finding a constant c and a point n?

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

-
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

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