**Introduction to Asymptotic Notation**

December 30, 1996

We use to mean `order exactly', O to mean `order at most', and to mean `order at least'.

**Definition of :**
Given nonnegative functions *f* and *g* defined on the
positive integers, we write if and only if there are
positive constants , , and a positive integer *N*
such that
,
whenever *n*>*N*.

**Definition of O:**
Given nonnegative functions *f* and *g* defined on the positive integers,
we write *f*=O(*g*) if and only if there is a positive constant *C* and an
integer *N* such that
, for all *n*>*N*.

**Definition of :**
Given nonnegative functions *f* and *g* defined on the positive integers,
we write if and only if there is a positive constant *C*
and an integer *N* such that
, for all *n*>*N*.

When using order notation, one wants to use the simplest function possible within the , O, or . The idea is to use the notation to reduce complicated functions to simpler ones whose behavior is easier to understand.

**Proposition 1**:
Suppose *f* and *g* are positive functions defined
on the positive integers, and that
,
for some nonzero *a*.
Then .

*Proof:*
means that for any *c*>0 there
is an integer *N* such that ,
for all .
If we chose then there is an *N* such that
for all .
So, ,
for all .

Proposition 1 is useful because there are many techniques, such as L'Hopital's rule, for evaluating limits. However, there are some instances where Proposition 1 cannot be used.

For example, , even though is undefined.

**Examples of :**
If *f*(*n*) = 3*n* + 6 and *g*(*n*) = *n*, then
, or , or ,
as can be seen by using , and *N*=5.

Notice that if then , since if there
are positive constants , and *N* such that
for all *n*>*N*, then
,
for all *n*>*N*.

. . .

**Useful Properties of :**

1. If and , then .

2. If and , then .

3. .

4. for any *a*,*b*>1.

5.

6. .

7. .

8. .

9. If , and , then .

**O and Notation**

It is not always possible to determine the behavior of an algorithm
using -notation.
For example, given a problem with *n* inputs, we may have
an algorithm to solve the problem which takes time when *n* is even
and *Cn* time when *n* is odd.
Or, we may only be able to prove that an algorithm
never uses more than time and never less than
*Fn* time.
In either circumstance we can claim neither nor
to be the order of the time usage of the algorithm.
O and notation will allow us to give at least partial information.

**Proposition 2:** Suppose *f* and *g* are positive functions
defined on the positive integers, and that
,
then *f*=O(*g*).

**Examples of O:**
3 *n* + 2 = O(*n*), since , for all .
100 *n* + 6 = O(*n*), since , for all .
O, since ,
for all .
O(1), since 3 *n* + 2 is not less than or equal to
*c* for any constant *c* and all .
O(*n*).
O.

**Proposition 3:** Suppose *f* and *g* are positive functions
defined on the positive integers, and that
,
then .

**Examples of :**
, since for all .
, since for all .
since
for all .
.
.

**Useful Properties of O and :**

1. if and only if *f*=O(*g*) and .

2. If *f*=O(*h*) and *g*=O(*h*) then *f*+*g*=O(*h*).

3. If and then .

4. If *f*=O(*g*) and *g*=O(*h*) then *f*=O(*h*).

5. If and then .

6. Suppose 0<*a*<*b*. Then O and .

7. Suppose 0<*a* and 1<*b*, then O and
.

8. Suppose 1<*c* and 0<*a*, then O and .

Mon Dec 30 13:26:11 EST 1996