1
$\begingroup$

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

  • 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$.2011-09-28
  • 0
    @André: you mean $n \ge 1$ - n positive assumes n integral, which is not stated.2011-09-28
  • 0
    @Mark: It’s strongly implied by the use of $n$ (rather than $x$, for instance).2011-09-28
  • 0
    @Mark: The algorithms tag makes $n$ integral.2011-09-28
  • 0
    @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.2011-09-28
  • 0
    Agreed with all comments. I had a friend who wrote so that I couldn't distinguish his $x$ and $n$, which makes me a bit oversensitive to this.2011-09-28
  • 0
    @AndréNicolas yeah I think it's confusion over the variables. n^3 will always be larger than n^2, so why even need a c?2011-09-28
  • 0
    @MaxMackie: As a side note, it's easier to establish this by noticing that $ lim _{n \rightarrow \infty} (2n^2+n-8)/n^3 = 0$. So long as the right side is finite ,the criterion for being in $O(n^3)$ is satisfied2011-09-28
  • 0
    Replace $2n^2 +n-8$ by $100n^2+n-8$. We could either say that $100n^2 \le 100n^3$, $n\le n^3$ for all $n \ge $, so $100n^2+n-8< 101n^3$ for $n \ge 1$. Or else we could observe that $100n^2 +n -8 < n^3$ for $n \ge $101$. Either way we would have proved that $100n^2+n-8=O(n^3)$. In the second calculation, we improve the constant in front of the $n^3$, at the cost of "starting" at some later $n_0$. It doesn't matter, since $O$ doesn't care about constants. But for real analysis of algorithm, usually a big $O$ result comes first, improvement of constant next.2011-09-28

1 Answers 1

2

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

  • 0
    Ohhh, so once you've found a valid c, you simply sub in to find the value of n?2011-09-28
  • 0
    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$2011-09-28