Big O Notation and Polynomials
Date: 04/12/2001 at 10:17:29 From: Paul Statham Subject: Big O Notation and polynomials I have a sample question I have been practicing. It gives the function: f(x) = (x^3 - (4x^2) + 12)/(x^2 + 2) It then asks me to plot this on an Excel worksheet and explain the behaviour for increasing values of x, where 0 <= x <= 20 for intervals of 0.2. This part I have no problem with. It then tells me to find a polynomial function g(x) such that both these conditions apply. .f(x) is O(g(x)) .g(x) is O(f(x)) From this I presume that f(x) is the same as it was defined before, and have done the following calculations to get O(g(x)). For x > 1 we have the numerator x^3 - 4x^2 + 12 <= x^3 + 0 + 12x^3 For x > 2 we have the denominator x^2 + 2 <= x^2 + 2x^2 Hence we have |f(x)| <= 13x^3/3x^2 = 13x/3 giving f(x) as O(x) First of all, is that correct? And if it is, does it mean that g(x) = x ? This bit is confusing me because if that is the case, then how can g(x) be O(f(x)) ?
Date: 04/12/2001 at 17:31:19 From: Doctor Rob Subject: Re: Big O Notation and polynomials Thanks for writing to Ask Dr. Math, Paul. You have a minor problem in the above analysis because of the following fact. It is false that a <= b and 0 < c <= d implies that a/c <= b/d. (Try a = 9, b = 10, c = 1, d = 2.) What is true is that a <= b and c >= d > 0 implies that a/c <= b/d. Thus you need to find a function that is smaller than x^2 + 2, not greater, and still positive. x^2 will do, and then you get |f(x)| <= 13*x^3/x^2 = 13*x. This still gives f(x) = O(x), which is correct. To prove that x = O(f(x)), you need to find a constant C and a bound X such that x >= X implies that x <= C*f(x). One way I like to deal with rational functions is to divide the polynomial of larger degree by the one of smaller degree, with remainder, and express the function that way. In this case, f(x) = (x^3-4*x^2+12)/(x^2+2) = x - 6 + (2*x+4)/(x^2+2) Now I want to know when the fraction is smaller than a constant. The constant 2 happens to be convenient, but I could use any other positive one I want. That happens when (2*x+4)/(x^2+2) < 2 x + 2 < x^2 + 2 0 < x^2 - x which is true for all x > 1. Thus for all x > 1, f(x) < x - 4 < x. This proves that f(x) = O(x). On the other hand, the fraction is positive for all x > -2. That implies that for all x > -2, f(x) > x - 6. Now I want x - 6 > C*x for some C and all x >= X. That happens if and only if (1-C)*x > 6, that is, x > 6/(1-C) (for C < 1). That means that I can choose, for example, C = 1/2, and X = 12, and then for x >= 12, x - 6 >= (1/2)*x, so for x >= 12, f(x) > x - 6 >= (1/2)*x x < 2*f(x) This means that x = O(f(x)). You can choose g(x) = x. It may be worth noticing that *any* polynomial g(x) of degree 1 would do here. You would have to adjust the constants C and bounds X, but that does not affect the validity of the relation, which just needs them to exist, and doesn't specify their sizes. g(x) and f(x) can have that relation if |f(x)/g(x)| is bounded above and below by positive constants for large x. In this case, the constants 1 and 1/2 will do, and when you use those constants, "large" means x >= 12. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum