Upperbound confusion

Question

Why is the following true?

$3n^2-100n+6$ is big $O$ of $n^2$

This has been demonstrated to be true when $c$ is $4$ and $n$ is $10$.

$3*100-1000+6 = -694 = 694$ is the absolute value is a big $O$ of $4*100 = 400$

It looks like $n^2$ is a lot less. What am I doing wrong?

Answer 1

It seems like you are confused as to the definition of "big $O$". (either that or I'm confused)

$f(n)$ is big $O$ of $g(n)$ means $f(n)/g(n)$ is bounded. Since in your case $f(n)/g(n)=\frac{3n^2-100n+6}{n^2}$ converges to $3$, it is bounded.

I don't see where "$c$" comes into it.

Answer 2

Here is an example using the following definition of $f(n)$ in Big O $g(n)$: $f(n)$ in Big-O $g(n)$ if there exists positive constants $c, n_0$ such that $0 \leq f(n) \leq cg(n)$. Ok consider the functions $f(n) = 5n^2 -20n + 12$ and $g(n) = n^2$. $$f(n) = 5n^2 -20n +12$$ $$ \leq 5n^2 -20n + 12n,\ \ n \geq 1$$ $$ \leq5n^2 - 8n $$ $$\leq 5n^2$$ So, this is valid for $n_0 = 1$. So $5n^2 -20n + 12 \in O(n^2)$ because $0 \leq 5n^2 -20n +12 \leq 5n^2$ for $n_0 = 1$.

Now I'll use the other defintion to verify the same thing: $$|f(n)| = |5n^2 -20n +12|$$ $$\leq |5n^2| + |-20n| +|12|$$ $$\leq 5|n^2| + 20|n| + 12 $$ $$\leq 5|n^2| + 20|n^2| + 12|n^2| , n \geq 1 $$ $$\leq 37|n^2| $$ So, this is valid for $n_0 = 1$. So $5n^2 -20n + 12$ in Big O $n^2$ because $0 \leq |5n^2 -20n +12| \leq 37|n^2|$ for $n_0 = 1$. A specific constant $c$ and $n_0$ aren't really important, but the existence is what matters.

Answer 3

Here is an example using the following definition of f(n) in Big O g(n): f(n) in Big-O g(n) if there exists positive constants c, n_0 such that 0 < f(n) < cg(n). Ok consider the functions f(n) = 5n^2 -20n + 12 and g(n) = n^2.

f(n) = 5n^2 -20n +12

< 5n^2 -20n + 12n, n > 1

< 5n^2 - 8n

< 5n^2 So, this is valid for n_0 = 1. So 5n^2 -20n + 12 is in Big-O n^2 because 0 < 5n^2 -20n +12 < 5n^2 for n_0 = 1.

Now I'll use the definition that you use to verify the same thing: absoluteValue(f(n)) = absoluteValue(5n^2 -20n +12)

< absoluteValue(5n^2) + absoluteValue(-20n) +absoluteValue(12)

< 5absoluteValue(n^2) + 20absoluteValue(n) + 12

< 5absoluteValue(n^2) + 20absoluteValue(n^2) + 12absoluteValue(n^2) , n > 1

< 37absoluteValue(n^2)

So, this is valid for n_0 = 1. So 5n^2 -20n + 12 in Big O n^2 because 0 < absoluteValue(5n^2 -20n +12) < 37absoluteValue(n^2) for n_0 = 1. A specific constant c and n_0 aren't really important, but the existence is what matters.