# Big-O relationship proof

1. Dec 10, 2012

### nicnicman

1. The problem statement, all variables and given/known data
To establish a big - O relationship, find witnesses C and k such that |f(x)| <= C|g(x)| whenever x > k.

Show that x^3 is O(x^4) but that x^4 is not O(x^3).

2. Relevant equations
If f(x) is O(g(x)) then there is a C such that f(x) <= Cg(x).

3. The attempt at a solution

If f(x) is O(g(x)) then there is a C such that f(x) <= Cg(x).
Thus, if x^3 is O(x^4), then x^3 <= C(x^4).
This is true for all C > 0 when C is a real number.

Similarly, if x^4 is O(x^3) then
x^4 <= Cx^3.
x <= C (divide both sides by x^3)
However, x <= C can not be true for any C. Thus x^4 is not O(x^3).

I'm not sure about this proof because I didn't provide witnesses C and k as the instructions called for. Big-O problems confuse me and I'm not sure if this proof is correct. Any suggestions are appreciated.

2. Dec 11, 2012

### nicnicman

Any suggestions?

3. Dec 11, 2012

### clamtrox

What is true? x3≤Cx4 if and only if x ≥ 1/C. Perhaps this can help you to find some values of k and C.