How to determine whether a function ISN'T big-oh of another function

[vaderboi]

The below is information I posted in another thread that explains the background information of what I am studying and what I understand (I am still having trouble with understanding big-Oh concepts):

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 NOT big-Oh of the other. Proving that a function IS big-Oh of another function is relatively easier since you only need to find one positive constant C and k that allows one function to be big-Oh of another. But proving it isn't is harder because you have to establish that there exists no constants C and k that allow one function to be big-Oh of the other.

Here is how to figure out if a function is NOT big-Oh of another function according to the link provided above:

Example: The function f(x)=2x³+10x is not in O(x²).

Proof: Now we must show that no C and k exist to meet the condition from the definition.

For any candidate C and k, we can take x>k and x>0 and we would have to satisfy

//This is my note. The person who is posting on Free Math Help. These steps are labeled 1 to 4 for convenience in discussing them
|2x³+10x| < C|x²| //1
2x³+10x < Cx² //2
2x³ < Cx² //3
x < C/2 //4

So no such C and k can exist to let the inequality hold for large x.∎

What I am confused about is that I I don't understand how to get from step 2 to 3. Why is the 10x allowed to be removed? I have been researching this and wracking my brain but I don't get how you are allowed to get rid of it.

 

[Deleted member 4993]

The below is information I posted in another thread that explains the background information of what I am studying and what I understand (I am still having trouble with understanding big-Oh concepts):



What I am trouble with is understanding how to prove that one function is NOT big-Oh of the other. Proving that a function IS big-Oh of another function is relatively easier since you only need to find one positive constant C and k that allows one function to be big-Oh of another. But proving it isn't is harder because you have to establish that there exists no constants C and k that allow one function to be big-Oh of the other.



What I am confused about is that I I don't understand how to get from step 2 to 3. Why is the 10x allowed to be removed? I have been researching this and wracking my brain but I don't get how you are allowed to get rid of it.

Duplicate post of:

https://www.freemathhelp.com/forum/...ble-to-change-what-f-n-is.118479/#post-468951

 

[JeffM]

I do not think this is a duplicate. Part of it is a duplicate to avoid repitition.

We are dealing with positive numbers in a proof by contradiction.

The assumption posited for purposes of contradiction is

[MATH]|2x^3 + 10x| < C|x^2|.[/MATH]
[MATH]|2x^3 + 10x| = 2x^3 + 10x \ \because \ x > 0.[/MATH]
[MATH]\therefore 2x^3 + 10x < Cx^2 \ \because |x^2| = x^2.[/MATH]
[MATH]2x^3 < 2x^3 + 10x \ \because \ x > 0.[/MATH]
[MATH]\therefore 2x^3 < 2x^3 + 10x < Cx^2 \implies 2x^3 < Cx^2 \implies[/MATH]
[MATH]x < \dfrac{C}{2}.[/MATH]
I have merely made explicit what was implicit before, namely the condition that x, C, and k are positive.

 

[vaderboi]

Oh okay. x < C/2 is equivalent to 2x = C which means that the |2x³ + 10x| !< C|x² for any C and k because C is a function of x and not a constant. Do I have that right?

 

[JeffM]

Oh okay. x < C/2 is equivalent to 2x = C which means that the |2x³ + 10x| !< C|x² for any C and k because C is a function of x and not a constant. Do I have that right?

I am not quite sure.

Let C be any positive constant.

That entails that [MATH]x > 0 \text { and } |x^3 + 10x| < C|x^2| \implies x < \dfrac{C}{2} \implies[/MATH]
[MATH]|x| \not < \dfrac{C}{2} \text { if} x \not < {C}{2}.[/MATH]
Whatever positive number k is, there are values of x greater than or equal to k that fail the test.

 

[vaderboi]

Why can't C/2 be more than |x|? Say x = 5 and C = 20. In that case C/2 would equal 10 which would be multiplied by x. That's why I tried to find out what C would be equal to. If C = x then that's a nonsense statement because that means that C is a function of x and NOT a constant.

 

[vaderboi]

Nevermind. I just said it. C/2 can't be more than |x| because x will increase indefinitely whereas C will always stay the same. I understand.

 

[Steven G]

There is only reason why 2x³+10x <Cx² and that is because Cx²>2x³+10x.
Now 10x >0 so if you remove 10x from the ineaquality then Cx² is surely greater than 2x³

We know that 15> 3+10 then surely 15>3.
Stop searching the web for answers and think.

 

[vaderboi]

I think it is very rude to assume I haven't been thinking. I come on here when I've hit a brick wall. What is wrong with that? It is akin to talking to a tutor who will help explain something to you. Regardless of the method of learning, I am still the one who has to eventually understand the concepts. Why is reading an article different from asking a person for help? Both depend on the knowledge of other people. This forum has genuinely helped me understand these concepts better.

Don't know if that was a typo, but there is no C and k that exists that makes |x^2| greater than or equal to |2x^3|