- #1
nicnicman
- 136
- 0
Homework Statement
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).
Homework Equations
If f(x) is O(g(x)) then there is a C such that f(x) <= Cg(x).
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.