Upperbound confusion 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?
 A: 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.
A: 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.
A: 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.
