Associated Topics || Dr. Math Home || Search Dr. Math

### 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/

Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search