# Big O - Explanation needed

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jul 31st 2009, 11:29 AM
JTG2003
Big O - Explanation needed
I'm reading through a discrete math book and it's talking about Big O notation. The concept makes sense to me, but I don't understand how they're applying it. They give examples and state things to be true and don't explain it.

An example they give is

"Show that f(x) = x^2 + 2x + 1 is O(x^2)"

This is saying.. what, exactly? Show that the first equation is related to x^2 by use of witnesses? .. I don't even know what that means.

"Solution: We observe that we can readily estimate the size of f(x) when x>1 because x<x^2 and 1<x^2. It follows that

0 <= x^2 + 2x + 1 <= x^2 + 2x + x^2 = 4x^2

whenever x > 1."

I have no idea what they did here or how they came up with "4x^2". Why would they replace 1 with x^2?

Any information would be appreciated.
Thanks
• Jul 31st 2009, 11:56 AM
AlephZero
Quote:

Originally Posted by JTG2003
I'm reading through a discrete math book and it's talking about Big O notation. The concept makes sense to me, but I don't understand how they're applying it. They give examples and state things to be true and don't explain it.

An example they give is

"Show that f(x) = x^2 + 2x + 1 is O(x^2)"

This is saying.. what, exactly? Show that the first equation is related to x^2 by use of witnesses? .. I don't even know what that means.

"Solution: We observe that we can readily estimate the size of f(x) when x>1 because x<x^2 and 1<x^2. It follows that

0 <= x^2 + 2x + 1 <= x^2 + 2x + x^2 = 4x^2

whenever x > 1."

I have no idea what they did here or how they came up with "4x^2". Why would they replace 1 with x^2?

Any information would be appreciated.
Thanks

Apparently there is a typo. They mean:

$x>1\implies x and $1 so that

$0\leq x^2+2x+1 \leq x^2 +2x^2 + x^2 = 4x^2.$
• Jul 31st 2009, 12:03 PM
JTG2003
Quote:

Originally Posted by AlephZero
Apparently there is a typo. They mean:

$x>1\implies x and $1 so that

$0\leq x^2+2x+1 \leq x^2 +2x^2 + x^2 = 4x^2.$

Uhm.. I'll keep that in mind .. doesn't seem to clarify much though.
• Jul 31st 2009, 12:07 PM
AlephZero
It occurs to me that maybe my above post didn't explain much. So I'll try to flesh things out a bit for you.

I've seen a few different definitions of Ordo ("Big Oh"), but here's a common one: "Let $f(x)$ and $g(x)$ be nonnegative functions of $x$. We say that

$f(x)$ is $O(g(x))$

provided that

$f(x)\leq Kg(x)$

for some constant $K$ and $x$ sufficiently large."

In other words, we need to find a $K.$ In your example, they used simple arguments from inequalities to arrive at $K=4.$ Now that the typo is cleared up, do you see what they did? Post again if you're still confused.

Cheers.
• Jul 31st 2009, 12:20 PM
JTG2003
Quote:

Originally Posted by AlephZero
It occurs to me that maybe my above post didn't explain much. So I'll try to flesh things out a bit for you.

I've seen a few different definitions of Ordo ("Big Oh"), but here's a common one: "Let $f(x)$ and $g(x)$ be nonnegative functions of $x$. We say that

$f(x)$ is $O(g(x))$

provided that

$f(x)\leq Kg(x)$

for some constant $K$ and $x$ sufficiently large."

In other words, we need to find a $K.$ In your example, they used simple arguments from inequalities to arrive at $K=4.$ Now that the typo is cleared up, do you see what they did? Post again if you're still confused.

Cheers.

Sorry, I'm not really great with math .. I seem to be missing something.

I know big O notation can be used to describe relationships between algorithms from a computing stand point. So, if you have an algorithm running on an old computer, you can use big O notation to describe how it will run on newer equipment based on constants rather than the numbers being computed.

This being said, I'm trying to understand the actual meaning of

Quote:

Originally Posted by AlephZero
$f(x)$ is $O(g(x))$

provided that

$f(x)\leq Kg(x)$

So, one function (f(x)) is Big O of another function (g(x)) if the first function is less than the second using a constant?

I seem to be hitting some kind of roadblock here. I see all the inequalities and functions and Big O notations, but I have no idea what they mean.

I suppose that would be the place to start.

Unfortunately there seems to have been a TV show called "Big O" and it is clouding all my searches.
• Jul 31st 2009, 12:30 PM
AlephZero
Never fear, we'll get it sorted out for you. Okay. You're given a function $f(x)$ and asked to show that it is "Big Oh" another function $g(x).$ This means you need to show there is some constant $K,$ it doesn't matter how large or small so long as it is positive, such that $f(x)\leq Kg(x)$ for $x$ sufficiently large. This last part means "eventually," more or less; in other words, there is a point beyond which any value of $x$ will make the inequality true.

So in your example, they give you $f(x),$ $g(x)$ is $x^2,$ and " $x$ sufficiently large" is just going to be $x>1.$

Now, when $x>1,$ the following inequalities are always true:

$x^2 \leq x^2, \quad 2x<2x^2, \quad 1

This is just how squaring works. You can prove these inequalities in various ways depending on where you are in your math education, but it's good to just know them. If you want to learn how to prove them, post again.

Now all that's left is to link all these inequalities into a sort of chain, so that

$f(x)=x^2 + 2x +1 \leq x^2 + 2x^2 + x^2 = 4x^2=4g(x).$

Now we've found a $K = 4$ such that for all $x>1,$ we have $f(x)\leq Kg(x),$ and we're done.
• Jul 31st 2009, 12:45 PM
JTG2003
Quote:

Originally Posted by AlephZero
$x^2 \leq x^2, \quad 2x<2x^2, \quad 1

Ok.. so when x>1, I can see how these are true.

Quote:

Originally Posted by AlephZero
Now all that's left is to link all these inequalities into a sort of chain, so that

$x^2 + 2x +1 \leq x^2 + 2x^2 + x^2 = 4x^2.$

Now we've found a $K = 4$ such that for all $x>1,$ we have $f(x)\leq Kg(x),$ and we're done.

So since
$1 \leq x^2$
then follows that
$x^2 + 2x +1 \leq x^2 + 2x^2 + x^2$
since the 1 in the second part has been replaced with $x^2$

Question 1) Why replace the 1? Because it is a constant and won't have any impact when x is sufficiently large?

I see what has been done, and that you have created an inequality that is true, but what was the reasoning behind replacing 1 with $x^2$?

Question 2) .... still no idea where the $4x^2$ came from.
K is our constant ... but it shows up nowhere in the inequality.
Does $f(x)\leq Kg(x),$ mean K * g(x)? With g(x) being $x^2 + 2x^2 + x^2$?

So we're looking for a number for K that will make this statement true? But I thought it was always true for x>1 ....
• Jul 31st 2009, 12:53 PM
AlephZero
Quote:

Originally Posted by JTG2003
So since
$1 \leq x^2$
then follows that
$x^2 + 2x +1 \leq x^2 + 2x^2 + x^2$
since the 1 in the second part has been replaced with $x^2$

Question 1) Why replace the 1? Because it is a constant and won't have any impact when x is sufficiently large?

I see what has been done, and that you have created an inequality that is true, but what was the reasoning behind replacing 1 with $x^2$?

Question 2) .... still no idea where the $4x^2$ came from.
K is our constant ... but it shows up nowhere in the inequality.
Does $f(x)\leq Kg(x),$ mean K * g(x)? With g(x) being $x^2 + 2x^2 + x^2$?

So we're looking for a number for K that will make this statement true? But I thought it was always true for x>1 ....

1. We aren't really "replacing" 1 with $x^2,$ we're just proving that $1 The "linking" of inequalities comes from this rule: $a, $c and $e implies that $a+c+e So we've taken the three inequalities, and sort of added them together.

2. We've shown using the inequalites that $f(x)\leq 4g(x).$ Thus we've found a $K,$ which is equal to 4.

Make sense?
• Jul 31st 2009, 01:06 PM
JTG2003
Quote:

Originally Posted by AlephZero
1. We aren't really "replacing" 1 with $x^2,$ we're just proving that $1 The "linking" of inequalities comes from this rule: $a, $c and $e implies that $a+c+e So we've taken the three inequalities, and sort of added them together.

Ok, got it.

Quote:

Originally Posted by AlephZero
2. We've shown using the inequalites that $f(x)\leq 4g(x).$ Thus we've found a $K,$ which is equal to 4.

Make sense?

$x^2 + 2x +1 \leq x^2 + 2x^2 + x^2$

... OH. Yes. Kind of. $x^2 + 2x^2 + x^2 = 4x^2$
Somehow.. with all these numbers I didn't even realize the second half of the inequality was all $x^2$'s. So.. just combine like terms..

Ok, so in f(x), $x^2$ is clearly the driving force. So we compare it to g(x) using only $x^2$ to derive the constant, 4..?
• Jul 31st 2009, 01:15 PM
AlephZero
Quote:

Originally Posted by JTG2003
Ok, so in f(x), $x^2$ is clearly the driving force. So we compare it to g(x) using only $x^2$ to derive the constant, 4..?

Yes, now you've got it. As long as $x>1$, $f(x)=x^2+2x+1$ is always going to be less than $x^2+2x^2+x^2=4x^2=4g(x).$ So we've found a constant such that $f(x)$ is eventually always less than this constant multiplied by $g(x).$

You're correct that the $x^2$ is the driving force, because that's our value of $g(x).$ When analyzing $f(x),$ we need to look for how it relates to our $g(x).$

I hope that clears it up for you. Please let us know if you're still unsure about something.
• Jul 31st 2009, 01:57 PM
JTG2003
One more thing. What is a "witness"?

From the book:

"Consequently, we can take C = 4 and k = 1 as witnesses to show that f(x) is O( $x^2$). That is, f(x) = $x^2 + 2x + 1 < 4x^2$ whenever x > 1."

Any idea what they're referring to?

I lied.. another question:

"Alternatively, we can estimate the size of f(x) when x > 2. When x > 2, we have $2x \leq x^2$ and $1 \leq x^2$. Consequently, if x > 2, we have

$0 \leq x^2 + 2x + 1 \leq x^2 + x^2 + x^2 = 3x^2$

It follows that C=3 and k=2 are also witnesses to the relation f(x) is O(x^2)."

Again with the witnesses ...

Are the constants always integers?
• Jul 31st 2009, 02:04 PM
AlephZero
Quote:

Originally Posted by JTG2003
One more thing. What is a "witness"?

From the book:

"Consequently, we can take C = 4 and k = 1 as witnesses to show that f(x) is O( $x^2$). That is, f(x) = $x^2 + 2x + 1 < 4x^2$ whenever x > 1."

Any idea what they're referring to?

I lied.. another question:

"Alternatively, we can estimate the size of f(x) when x > 2. When x > 2, we have $2x \leq x^2$ and $1 \leq x^2$. Consequently, if x > 2, we have

$0 \leq x^2 + 2x + 1 \leq x^2 + x^2 + x^2 = 3x^2$

It follows that C=3 and k=2 are also witnesses to the relation f(x) is O(x^2)."

Again with the witnesses ...

Are the constants always integers?

1. I've never heard the term "witness" used in this context before (it is sort of novel though... I may consider adopting it), but I know what they mean. Their $C$ is our $K$, the constant we used to prove $f(x)\leq Kg(x),$ and their $k$ is used in the context of what I called "sufficiently large;" i.e., the inequality we found was true when $x>1,$ and they're calling $k=1.$ (So their "sufficiently large" is something like, "there exists a constant $k$ such that for all $x>k,$ the inequality holds.")

2. They're doing exactly what we did, except they've found different inequalities to use. Do you understand how they came up with that particular set of inequalities? Post if you don't see why they're true.

Cheers.
• Jul 31st 2009, 02:09 PM
JTG2003
Yup, got it. I got a little mixed up because we used k instead of C.

Ok, I'm gonna see if I can finish this section without getting caught op on details for another 4 hours.

• Jul 31st 2009, 02:23 PM
AlephZero
Quote:

Originally Posted by JTG2003
Yup, got it. I got a little mixed up because we used k instead of C.

Ok, I'm gonna see if I can finish this section without getting caught op on details for another 4 hours.

Glad to be of help! Incidentally, I'm sure it's just a caps error, but just to clarify, we used K (in caps) instead of C... so their C is our K and our "sufficiently large" is their k (in lowercase)... just so you don't confuse them.

Feel free to post again if you need more help on these. Should probably start a new thread, though, as the moderators largely frown on posting multiple problems in a single thread.

Good luck!
• Jul 31st 2009, 11:15 PM
CaptainBlack
Quote:

Originally Posted by JTG2003
I'm reading through a discrete math book and it's talking about Big O notation. The concept makes sense to me, but I don't understand how they're applying it. They give examples and state things to be true and don't explain it.

An example they give is

"Show that f(x) = x^2 + 2x + 1 is O(x^2)"

This is saying.. what, exactly? Show that the first equation is related to x^2 by use of witnesses? .. I don't even know what that means.

"Solution: We observe that we can readily estimate the size of f(x) when x>1 because x<x^2 and 1<x^2. It follows that

0 <= x^2 + 2x + 1 <= x^2 + 2x + x^2 = 4x^2

whenever x > 1."

I have no idea what they did here or how they came up with "4x^2". Why would they replace 1 with x^2?

Any information would be appreciated.
Thanks

Big-O notation and the other related notations are used to describe the rate of growth of functions. You should know that as $x$ becomes large $x^n$ grows faster than $x^r$ for any $r. This means that whatever value of $k>0$ we use, eventually $k|x^r|<|x^n|$

When we write:

$f(x)=O(g(x))$

this is short hand (and abuse of notation as well) for $f(x)$ grows no faster than $g(x)$ as $x$ goes to infinity. This means that there is some $K$ such that eventually (that is for all $x$ big enough):

$|f(x)|\le K|g(x)|$

CB
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last