Proving that f = O(g) Whenever deg(f) <= deg(g)Date: 04/20/2010 at 15:40:15 From: Akram Subject: f=O(g) whenever deg(f)<=deg(g) , can we formally prove it ? It's common knowledge that f(n) = O(g(n)) whenever f(n) and g(n) are polynomials with deg(f) <= deg(g). Roughly speaking, I understand big O notation as saying that g(n) can eventully beat f(n) in terms of growth even with the help of a positive constant. By "eventually," I mean when n gets large enough, or when n >= n_0. (Sorry for the vulgar explanation, which needs to become more formal.) For example: if f(n)= 100n and g(n) = n^2, then f(n) = O(g(n)). This makes sense to me, and I can prove it algebraically by finding the two positive integers, C = 1 and n_0 = 100, such that 0 <= f(n) <= Cg(n) for all n >= n_0 And I can observe this relationship in the growth of the functions when I plot them together in any graphing software. But how can we generalize that f = O(g) whenever deg(f) <= deg(g)? and how can we formally prove this generalization? I tried mathematical induction to at least prove it for the natural number set, as follows: When n = 1, both f(n) and g(n) are constant functions, so f(n) = O(n) When f(n) = O(g(n)), deg(f(n + 1)) = deg(f(n)) AND deg(g(n + 1)) = deg(g(n)), So f(n) = O(n). I'm not sure about this proof. But even if it does work, it only holds for natural numbers, and I'm curious about other sets, like R. I really need your comment about it. Date: 04/28/2010 at 18:58:38 From: Akram Subject: f=O(g) whenever deg(f)<=deg(g) , can we formally prove it ? Your response is really appreciated. Date: 05/02/2010 at 20:03:27 From: Doctor Vogler Subject: Re: f=O(g) whenever deg(f)<=deg(g) , can we formally prove it ? Hi Akram, Thanks for writing to Dr. Math -- and for letting us know you're still interested in an answer. Sorry for the delay. Of course, we can prove this formally. It just takes a little careful analysis to figure out what the constants have to be. It might help to try this for a few specific examples first, like n^2 + 1 = O(n^2) or n^3 + n + 1 = O(n^3 - 1). If you can formally prove it for a particular pair of functions, then try a harder pair (or, in any case, another pair) until you figure out a strategy that will work for all pairs of polynomials. Rather than leave you only with that advice (which is still good advice; try something similar before asking your next question), I'll offer a general strategy. Let d = deg(g), so that deg(f) <= d. Also let M be the sum of the absolute values of all of the coefficients of f(n). It follows that |f(n)| <= M*n^d whenever n >= 1. Can you explain why? (Hint: start with the triangle inequality.) Next, let A be the leading coefficient of g(n) and let B be the sum of the absolute values of all of the *other* coefficients of g(n). Now explain why A is nonzero and |g(n) - A*n^d| <= B*n^(d - 1) whenever n >= 1. It follows that, in particular, -(g(n) - A*n^d) <= B*n^(d - 1). The above is true in either case; but in the following, I will assume that A > 0. (If A < 0, then you could just use the argument with g(n) replacing -g(n), and then take the final C and negate it. But it would be a little funny to use a negative function in a big-O.) And of course, B >= 0 by definition. Next, use the previous inequality to prove that, when n >= 1, A*n^d - B*n^(d - 1) <= g(n). Now all we need to do is get M*n^d <= C*(A*n^d - B*n^(d - 1)), and then we'll be done! If it weren't for that pesky B, then we could just take C = M/A. But B might actually be larger than A, so we can't simply subtract B from A. Fortunately for us, B is the coefficient of a lower-degree term, and we can use that to our advantage. Let's require n be large enough that the B term doesn't reduce the A term by more than 1/2. That results in the following argument: Let n_0 = max(1, 2B/A). If n >= n_0, then we have n >= 2B/A (A*n)/2 >= B (A*n^d)/2 >= B*n^(d - 1) A*n^d - (A*n^d)/2 >= B*n^(d - 1) A*n^d - B*n^(d - 1) >= (A*n^d)/2 Now we take C = 2M/A. Since n >= n_0 >= 1, we have |f(n)| <= M*n^d = (A*C/2)*n^d = C*(A*n^d)/2 <= C*(A*n^d - B*n^(d - 1)) <= C*g(n). And there we have it! If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/