Proving O(n)Date: 01/23/2001 at 12:14:01 From: Shawn Marriott Subject: Proving O(n) How would you prove that an equation is of order n, or n squared? Ex: 3n(squared) -31n + 100 O(n square) Date: 01/23/2001 at 16:17:21 From: Doctor Rob Subject: Re: Proving O(n) Thanks for writing to Ask Dr. Math, Shawn. You need to show that there are real number C > 0 and natural number N such that whenever n >= N, then |3*n^2 - 31*n + 100| <= C*n^2. Pick a real number C larger than the absolute value of the coefficient of n^2 in the polynomial, in this case 3. Any C will work, but the larger it is, the easier. I would pick 200, larger than the sum of all the coefficients. Then I want to show that there is an N such that for all n >= N, 3*n^2 - 31*n + 100 <= 200*n^2. That can be transformed into the equivalent 100 - 31*n <= 197*n^2. This will be true if the stronger condition holds, 100 <= 197*n^2, 100/197 <= n^2. (This is stronger because 100 > 100 - 31*n.) Again we can replace this with a stronger condition, 1 <= n^2, 1 <= n. (This is stronger because 100/197 < 1.) That means that we can take N = 1, and then for every n >= N, 3*n^2 - 31*n + 100 <= 200*n^2. That proves that 3*n^2 - 31*n + 100 = O(n^2). If you picked the real number 4 instead of 200, you would get the condition 3*n^2 - 31*n + 100 <= 4*n^2, 0 <= n^2 + 31*n - 100, 1361 <= (2*n+31)^2, 36.9... <= 2*n + 31, 2.9... <= n, so we can take N = 3. Then for all n >= N, 3*n^2 - 31*n + 100 <= 4*n^2, That proves that 3*n^2 - 31*n + 100 = O(n^2). The closer to 3 you choose C, the larger N will have to be to complete your proof. Fortunately, you don't care how large N is, just that it exists. In this case, you could actually choose C = 3. Then the condition you need is 3*n^2 - 31*n + 100 <= 3*n^2, 100 <= 31*n, 100/31 <= n, so we could take N = 4. If you try a number smaller than 3, you'll find that no value of N will work. For example, if we choose C = 2, then the condition will be 3*n^2 - 31*n + 100 <= 2*n^2, n^2 - 31*n + 100 <= 0. This fails whenever n is larger than the largest root of the polynomial on the left, that is, when n >= 28. - Doctor Rob, 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/