1. ## Big Oh Notation

Hi guys,
I was wondering if someone could explain to me how Big Oh notation works in plain english. after reading many articles, watching videos and reading text book chapter over and over, i am still not 100% clear. First of all, let me tell you what I understand so far:
Big Oh notation gives you the upper bound of a function. I understand that f(x) is O(g(x)) if there are constants C and k such that f(x) is less than or equal to C.g(x) whenever x > k

I guess my main problem is I am not sure how people actually come up with the 2 constants.It seems like everyone has their own way of solving it. Can someone please give me the easiest way to remember how to come up with the 2 witnesses.

For example: Show that f(x) = x^2+2x+1 is O(x^2)

one of the tutorials i was looking at suggested we only pay attention to the highest term. in this case x^2. and since x^2 has a coeffiecient of 1, that becomes one of the constant C. we then get k by adding all the terms of f(x) and pretending they all have x^2. i.e x^2+2x^2+1x^2 = 4x^2. Then we get 4 as the other constant and we have C = 1, k = 4.

however, in my textbook they have the following solution:

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.

I get lost at the very first part where it says we can readily estimate the size of f(x) when x > 1 because x < x^2..... where are they getting x from?

i feel like i have some kind of mental block because i understand the concept but not sure HOW to go about showing it..

any help would be really appreciated!! sorry for a loooong posting.. thanks!

2. O(h) essentially means that the quantity goes to zero at the same rate as h. Or that the quantity is similar in magnitude as h.

The x<x^2 is coming from the 2x in f(x). Here they are saying that when x>1 we know that x^2>x and therefore 2x^2 > 2x. You can then apply this reasoning to the constant in f(x), i.e. when x>1 x^2>1. Putting all this together we have that x^2+2x+1 < x^2 +2x^2 +x^2 = 4x^2.

3. The most simple way to explain it is an example: Imagine you write some piece of software. The calculations that must be done to run your software is dependend on your input value. Let's say, x describes how many possible combinations of streets you must compare for your car's navigation system to get from A to B and this number will not be linear but will be described by some function, e.g. $6x^4 - 2x^3 + 5$ (Wikipedia example). Then for large x you will not bother too much about the $2x^3$ part of this function anymore since then $6x^4$ grows way much faster and will mostly determine what you need to compute.

Now we do some simple math:

$|6x^4 - 2x^3 + 5| \le 6x^4 + |2x^3| + 5\\
\le 6x^4 + 2x^4 + 5x^4\\
= 13x^4\\
= 13|x^4|$

Now for high x this function will less and less differ from its (somehow least) upper bound (in power). And usually you are mostly interessted what will happen for large x since this is time you actually worry about. (You do not wanna wait for hours for your route to be computed.) So you summerize all these function in a common class so it becomes easier to stress that they somewhat belong together and all they will need to have in common to be "similar" is the upper bound (not considering the multiplicational factor (13) since again, this is not too important for large numbers and we don't want to bother if e.g. 12x^4 is an upper bound too (that is even lower).

4. thank you ivleph and raphw. i really appreciate your help. just have one more question. both of you added all the terms using the highest exponents to get the constant C which was 4 in the original example and 13 in the example that raphw provided. Now im trying to relate that to the following example from the book:

(this is just a continuation of the original example i provided).....

(paraphrased from the textbook)....

alternatively, we can estimate the size of 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. it follows that C = 3 and k = 2 are also witnesses to the relation f(x) is O(x^2)

I understand that we only need to find ONE pair of witness and since we already determined from original example that 4 and 1 are witnesses to this relationship, there are many other pairs of witnesses. once again, i understand the logic but can't figure out how the book gets 3x^2 from.

i guess the part that im confused at is, i understand how in original example we got x^2+2x+1 < x^2 +2x^2 +x^2 = 4x^2. but for the same terms, we now have x^2+2x+1 < x^2+x^2+x^2 = 3x^2 this time when x > 2.

5. However, here we have the additional assumption: 2x < x^2 and x > 2 > 1 which is why we can solve as the book did. Not that it would make much of a difference for the actual result. This is valid for all n > 2

6. Originally Posted by raphw
However, here we have the additional assumption: 2x < x^2 and x > 2 > 1 which is why we can solve as the book did. Not that it would make much of a difference for the actual result. This is valid for all n > 2
thanks again!

7. Originally Posted by lvleph
O(h) essentially means that the quantity goes to zero at the same rate as h. Or that the quantity is similar in magnitude as h.
Nonsense, $f(x)\in O(g(x)$ means that as $x \to \infty$

$\dfrac{|f(x)|}{g(x)}$

is bounded. That means that $|f(x)|$ grows no faster (up to a multiple) than $g(x)$

Hence if $f(x)\in O(x)$ then $f(x) \in O(x^n)$ for all $n\ge 1$. In other words $O(x)\subseteq O(x^n)$ for all $n\ge 1$

(with some qualification and abuse of notation big-O notation can be adapted for x approaching other values)

CB

8. Originally Posted by lvleph
O(h) essentially means that the quantity goes to zero at the same rate as h.
Originally Posted by CaptainBlack
That means that $|f(x)|$ grows no faster (up to a multiple) than $g(x)$
How are these really different? Sure I suppose it doesn't necessarily imply anything about going to zero, but in applied mathematics (which is my field, we always think about things going to zero or the true solution). The important portion of what I was saying was that the portion about rates.

9. Originally Posted by lvleph
How are these really different? Sure I suppose it doesn't necessarily imply anything about going to zero, but in applied mathematics (which is my field, we always think about things going to zero or the true solution). The important portion of what I was saying was that the portion about rates.
One says the relevant ratio goes to zero, while the other makes no such assertion but only claims it does not grow beyond some value.

CB