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:
(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:
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?
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?