1. ## Big O Notation

Hello all,

I've read some of the previous posts in regards to the Big O Notation and this seems to remain my achillies heel in terms of discrete math.

The given function is my book is this:

|f(x)| <= C|g(x)| when x > k (as I've seen on other posts as well).

My confusion comes from the first example in the book, given here:

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

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

0 <= x^2 + 2x + 1 <= x^2 + 2x^2 + x^2 = 4x^2 whenever x > 1. Consequently, we can take C = 4 and k = 1 as witnesses. That is f(x) = x^2 + 2x + 1 < 4x^2 whenever x > 1.

Alternately, we can estimate f(x) when x > 2. When x > 2, we have 2x <= x^2 and 1 <= x^2. Consequently, if x > 2, we have

0 <= x^2 + 2x + 1 <= x^2 + x^2 + x^2 = 3x^2, C = 3 and K =2

End Solution

I don't really understand the x > 1, x < x^2 and 1 < x^2 when x > 1 part, nor do I seem to understand how they reach x^2 + 2x^2 + x^2. Same goes for x > 2.

Anyone able to explain the above?

Thanks!

W
(First post!)

2. Originally Posted by Wiredg
Hello all,

I've read some of the previous posts in regards to the Big O Notation and this seems to remain my achillies heel in terms of discrete math.

The given function is my book is this:

|f(x)| <= C|g(x)| when x > k (as I've seen on other posts as well).

My confusion comes from the first example in the book, given here:

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

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

0 <= x^2 + 2x + 1 <= x^2 + 2x^2 + x^2 = 4x^2 whenever x > 1. Consequently, we can take C = 4 and k = 1 as witnesses. That is f(x) = x^2 + 2x + 1 < 4x^2 whenever x > 1.

Alternately, we can estimate f(x) when x > 2. When x > 2, we have 2x <= x^2 and 1 <= x^2. Consequently, if x > 2, we have

0 <= x^2 + 2x + 1 <= x^2 + x^2 + x^2 = 3x^2, C = 3 and K =2

End Solution

I don't really understand the x > 1, x < x^2 and 1 < x^2 when x > 1 part, nor do I seem to understand how they reach x^2 + 2x^2 + x^2. Same goes for x > 2.

Anyone able to explain the above?

Thanks!

W
(First post!)

If $x>1$ then $x^2>x>1$, since

Suppose:

$
x>1
$

multiply both sides by $x$ to get:

$x^2>x$

CB

3. ## Big O notation question

hi, I am weak in big-O notation too.

I do don't think u have explicitly addressed the "how they reach x^2 + 2x^2 + x^2" part of the question.

Also, after the explanation of x>1, where did the 0 in "0 <= x^2 + 2x + 1 <= x^2 + 2x^2 + x^2 = 4x^2" come from??

thank you so much for taking your time to answer this question.

4. Here is what you have to think about when it comes to Big O notation.

f(x)<=C*g(x)

C is a constant that is bigger than 0 and x > k. For it to be big O, then for all x that is greater than k, this equation has to hold true.

So for this: f(x) = x^2 + 2x + 1 is O(x^2).

You get: x^2 + 2x+ 1 <= C*x^2, if you remove the x^2 from the left side, you get 2x+1 <= (C-1)*x^2. You know that x^2 has a higher order of growth than 2x, so as x continues to get larger, x^2 will be bigger than 2x+1. As for C, you can pretty much just pick whatever number that works, the same for k. The important thing is that this has to be true for every possible x value greater than k, not just 1 value.

5. hi daibotcom, i understand your explanation. But i still cannot follow the example given by the first poster.

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

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

First, what does it mean " we can readily estimate the size of f(x) when x>1 ? why can't we readily estimate the size of f(x) when x=1 or x<1 ?

CaptainBlack has done an excellent job in explaining how we get x<x^2 and 1<x^2.

However, I do not understand the part that comes after "It follows that...."
Specifically, where did x^2 + 2x^2 + x^2 come from and how can it later become x^2 + x^2 + x^2 ?

6. "Specifically, where did x^2 + 2x^2 + x^2 come from and how can it later become x^2 + x^2 + x^2 ?"

You just make it up, you just need to make up some expression that would make the inequality true. x^2 + 2x^2 + x^2 was just made up, it equals 4x^2, so for that inequality, the 4 would be the "constant". And then you just need to find a number that x has to be bigger than, and no matter how much bigger that x is from the number you chose, the expression is always true.

7. isn't there a systematic manner to go about looking for C and k instead of just making up expressions?

8. You can always try simplifying the equation or adding terms, there isn't a set way to do it. The definition gives you a lot of room to do what you want to get it to work, there isn't a specific answer that works, there are tons.

9. so if we can simply make up equations, what use is C and k in big O notation?

10. You come up with the equations based on the C and k values you make up. These problems aren't ones where you just go in and solve for 1 answer and that is the only correct one, you are just looking for a C and k value that makes the inequality true, if it makes it true for all x > k for a given C, then you proved the definition.

11. Thks for the explanation, really appreciate it.