1

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?

Peter Mortensen
  • 670
user235991
  • 57
  • 1
    Why are you taking the absolute value of $-694$? – user222031 May 17 '15 at 13:15
  • @user222031 According to this I should do that. I'm not really sure how to go about it though. – user235991 May 17 '15 at 13:18
  • Oh the definition I use goes like this: $f(n) \in O(g(n))$ if there exists positive constants $c, n_0$ such that $0 \leq f(n) \leq cg(n)$ for $n \geq n_0$. How did you find your $c$ and $n_0$? How do you know they are valid with your definition? – user222031 May 17 '15 at 13:32
  • @user222031 ok can you provide an example using that definition? I can't find why the example in my question is true. If we're not getting the absolute value, is it because -694 is less than 400? – user235991 May 17 '15 at 13:33
  • I graphed it, and if your $c = 4$ your $n_0$ should at least be $15$ – user222031 May 17 '15 at 13:37

3 Answers3

2

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.

Gregory Grant
  • 14,874
  • 1
    more likely I'm confused. As I understand it, f(n) is big O of g(n) if there is a constant and some large value of n that when you do c*g(n) is always greater than f(n). – user235991 May 17 '15 at 13:21
  • Yes you are correct. So since the limit $f(n)/g(n)$ is 3, you can take $c=4$ and then there must be an $N\in\Bbb N$ such that $f(n)/g(n)\leq 4$ for all $n\geq N$. – Gregory Grant May 17 '15 at 13:44
  • f(n)/g(n)≤4 I'm not sure, do you you mean divide it? – user235991 May 17 '15 at 14:00
  • I mean if a sequence $a_n$ converges to $3$ that for sufficiently large $n$ we must have $a_n< 4$. You can replace $4$ by $3.00001$ if you want, as long as it's bigger than $3$. – Gregory Grant May 17 '15 at 14:03
  • ok, but I'm still confused when n = 10 in my question. And I think the answer to f(n) is -694. Is that really the right value? – user235991 May 17 '15 at 14:10
  • Big O really is for comparing two functions that are non-negative, or at least are both non-negative for all but finitely many (initial) values of $n$. In your case the first few values of $f$ may contain negatives but it doesn't matter because at some point it becomes positive and you look for your constants after that point. The point is that for all sufficiently large $n$ the bound $c=4$ holds. That implies that there is a universal bound $C$ that works for all $n$ since there are only finitely many $n$ that don't work for $c=4$. – Gregory Grant May 17 '15 at 14:14
  • so that's it. for few values of n it would be really negative. I thought we should get the absolute values of the negatives. So in my example, the relationship is true. Do you find anything else wrong in how I check the formula? – user235991 May 17 '15 at 14:23
  • Yes, don't mention $n=10$, that's just one value and you need the whole tail, so just say for $n>>0$ we can take $c=4$. – Gregory Grant May 17 '15 at 14:24
  • @user222031 Right, because that means there's another value of $c$ that works for all $n$. Usually you don't need that value of $c$ though, the one that works in the limit is almost always enough for whatever purposes one is using big O for. – Gregory Grant May 17 '15 at 14:28
  • I think I'm getting it. Just to confirm, did you get the limit 3 from 3n^2? And since 3 is the limit, any c greater than 3 would be fine? – user235991 May 17 '15 at 14:30
  • @user235991 Yes, that $3$ is why the limit of the ratio goes to $3$, it's crucial however that the power of $n$ is $2$ on both sides, if it was $3n^3$ on the left and $n^2$ on the right then it would not be big O, the limit of the ratio would be infinity. – Gregory Grant May 17 '15 at 14:32
  • what if it's the opposite. 3n^2 on the left and n^3 on the right? – user235991 May 17 '15 at 14:38
  • @user235991 Then it would be Big-O. Since the limit approaches 0. – user222031 May 17 '15 at 14:40
1

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.

user222031
  • 1,011
1

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.

user222031
  • 1,011