I have a review problem I am having problems with. This is the problem:
Be able to show the function, g(x) is O(f(x)) numerically as we have done in class
Use the definition of O-notation to prove that 2x^2+3x+4 is O(x^2) (Do not use the theorem on polynomial orders)
This is what I have so far.
2x^2+3x+4 <= ax^2
(2x^2 is of the highest order in this problem)
(2x^2+3x+4)/ax^2 <=1 = 2x^2/ax^2 = 2/a
Then my prof said to let a=3 because it is larger than two. I am not sure where to go to from there.
To prove that 2x^2 + 3x + 4 is O(x^2) using the definition of O-notation, you need to find a constant, let's say C, such that for sufficiently large values of x, 2x^2 + 3x + 4 is always less than or equal to C * x^2.
Here's how you can proceed:
1. Start by expressing the inequality: 2x^2 + 3x + 4 ≤ C * x^2
2. Divide both sides by x^2 (assuming x ≠ 0, as we are considering sufficiently large values of x)
(2 + 3/x + 4/x^2) ≤ C
3. As x approaches infinity (sufficiently large values of x), the terms 3/x and 4/x^2 approach 0. Therefore, we can disregard them.
2 ≤ C
4. Choose a value for C that satisfies the inequality. In your case, your professor suggested letting a = 3.
Therefore, C = 3.
5. Now, you can conclude that for sufficiently large values of x, 2x^2 + 3x + 4 is O(x^2) with C = 3, as it satisfies the definition of O-notation.
To summarize, you have shown that 2x^2 + 3x + 4 is O(x^2) by finding a constant C (in this case, C = 3) such that for sufficiently large values of x, 2x^2 + 3x + 4 is always less than or equal to C * x^2.