To find whether f(N) is big-Oh of g(N), why are we able to change what f(N) is?

vaderboi

Junior Member
Joined
Jan 18, 2019
Messages
59
For context, I am majoring in Computer Science and am taking a Data Structures class. We are studying big-Oh notation which allows you to compare how one function grows compared to another. To find whether a function is big-Oh of another we would say that:
For functions f(x) and g(x), we will say that "f(x) is O(g(x))” [pronounced "(x) is big-oh of g(x)"] if there are positive constants C and k such that
|f(x)|≤C|g(x)| for all x>k.

(This definition found at https://www.cs.sfu.ca/~ggbaker/zju/math/growth.html)

I understand that for f(x) to be big-Oh of g(x) there must exist at least one corresponding C and k such that g(x) will grow either equally or faster than f(x) forever more when x becomes greater than k.

What I am trouble with is understanding how to prove that one function is big-Oh of the other. The example to prove that one function is big-Oh of another that the link I mentioned above provides confuses me. Here is it in its entirety:

Example: The function f(x)=2x3+10x is O(x3).
Proof: To satisfy the definition of big-O, we just have to find values for C and k that meet the condition.
Let C=12 and k=2. Then for x>k,
|2x3+10x|= 2x3+10x
<2x3+10x3
=|12x3|.∎
Note: there's nothing that says we have to find the best C and k. Any will do.
Also notice that the absolute value doesn't usually do much: since we're worried about running times, negative values don't usually come up. We can just demand that x is big enough that the function is definitely positive and then remove the |⋯|

My question is, why does changing 2x3 + 10x to 2x3 + 10x3 allow us to prove that f(x) is big-Oh of g(x) in this context? Why are we allowed to change it?
 
With [MATH]x>k=2[/MATH] then [MATH]10x <10x^3[/MATH]. You have [MATH]0 \le f(x) < 12x^3[/MATH]. Isn't that all you need?
 
The way you stated made me understand why it works, I think.

So since we know that 10x is less than 10x3. It would follow that 2x3 + 10x is less than 2x3 + 10x3. Since 2x3 + 10x3 is equivalent to |12x3| and C * x3 is equivalent to 12x3, it would follow that |2x3 + 10x| is less than C * |x3| for some C and some k.

Is my understanding correct here?
 
It looks like you are understanding it. Do you see that you have literally fulfilled the definition with [MATH]C = 12[/MATH] and [MATH]k = 2[/MATH]?
 
Yes. I did see that. But thank you for checking. Thanks for your help. That cleared it up for me.
 
Top