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/