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!