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

  • 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
    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