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?
 

LCKurtz

Junior Member
Joined
May 3, 2019
Messages
122
With \(\displaystyle x>k=2\) then \(\displaystyle 10x <10x^3\). You have \(\displaystyle 0 \le f(x) < 12x^3\). Isn't that all you need?
 

vaderboi

Junior Member
Joined
Jan 18, 2019
Messages
59
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?
 

LCKurtz

Junior Member
Joined
May 3, 2019
Messages
122
It looks like you are understanding it. Do you see that you have literally fulfilled the definition with \(\displaystyle C = 12\) and \(\displaystyle k = 2\)?
 

vaderboi

Junior Member
Joined
Jan 18, 2019
Messages
59
Yes. I did see that. But thank you for checking. Thanks for your help. That cleared it up for me.
 
Top