0

This formula is actually from a big $O$ notation example, but I am confuse about the mathematical formula.

I read that:

if $n$ and $c$ are $1$,

$3n^2 - 100n + 6$ is not a big o of $n^3$

or

$cn^3 \lt 3n^2 - 100n + 6$

I'm confused here, if we calculate:

$1\times 1^3 = 1$

$3 - 100 + 6 = -91$

Isn't the opposite is true?

hamid kamali
  • 3,201
user235991
  • 57
  • Big $O$ notation is primarily used for limiting behavior, not for some particular small values of $n$. You are misunderstanding what is meant by $3n^2-100n+6=O(n^3)$, see if your example actually dissatisfies definition of $O$ notation. – user160738 May 09 '15 at 15:38
  • @user160738 well, I'm just starting to learn big O notation and this is the example I got. Could you explain how to calculate this correctly? – user235991 May 09 '15 at 16:03

1 Answers1

1

In short, the mistake occurred because we need to look at absolute value.

The definition is: If $f(x)$ is $O(g(x))$, then for some $c,N\in\mathbb{R}$ we have $|f(x)|\le c|g(x)|$ for all $x\ge N$.

Now for our specific example, $f(n)=3n^2-100n+6$ and $g(n)=n^3$, so we have $f(1)=-91$ and $g(1)=1$. Now we need to check that $|f(1)|\le c|g(1)|$, which is not the case because $|f(1)|=91$ while $c|g(1)|=1\times 1=1$. Hence $N=c=1$ is not sufficient to prove that $f(n)$ is $O\left(n^3\right)$.

However, $3n^2-100n+6$ is certainly $O\left(n^3\right)$. If we choose say $c=3$ and $N=100$, then we have for every $n\ge N$ $$3n^3>3n^2>3n^2-100n+6>0$$ so we are done.

Peter Woolfitt
  • 21,114