Introduction to Asymptotic Notation
Dr. Russ Miller
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) = 3n + 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 
.