MATH 164, Spring 2001 Due Date: Name(s):
Honors Project 12: The Order of Functions
Objective
In certain applications in science and engineering, the behavior of a function f = f(x) for large values of
x (x > N for some N) or small values of x (|x| < for some > 0) in comparison to the behavior of another
function g = g(x) is important. In this project we discuss the notation and classification of functions that
are used in studying such behavior.
Narrative
The terms "large" and "small" are relative. To illustrate, type the command lines below into Maple in
the order in which they are listed; they produce a table of values for f(x) = x2
, g(x) = 2x
, and h(x) = xx
.
Observe that while 2x
and xx
are both larger than x2
for large x, xx
is considerably larger than either x2
or
2x
.
> restart:
> M := matrix(20,4,(Row,Col)->0):
> for N from 1 to 20 do
M[N,1] := N: M[N,2] := N^2: M[N,3] := 2^N: M[N,4] := N^N: od:
> eval(M);
Here is another example aimed at illustrating why this is important in a specific application: Suppose we
have several different algorithms for implementing the same task, and that we must repeat this task many
times. (The task might involve alphabetically ordering the names in a telephone book, for example.) To
simplify things, we assume that neither space nor resources are a limitation, and hence there is no issue
surrounding the scalability of our task. Depending on the algorithm we use, the time T it takes to complete
the task N times may vary directly with N, with N lg N, with N2
or with N3
. "What difference does this
make?" Well, suppose it takes 1 second to perform the task when N = 106
using the algorithm in which T
varies directly with N: T = kN. Then (since 1 = 106
k), it follows that k = 10-6
. Since we are assuming
our task is scalable, the constant of proportionality for the algorithm in which T varies directly with N lg N
is also k = 10-6
-- that is, T = kN lg N = 10-6
N lg N -- so using this algorithm it would take
T(106
) = 10-6
106
lg 106
= 6 lg 10 = 19.9 seconds.
Using the algorithm in which T varies directly with N2
it would take 11.5 days, and using the algorithm in
which T varies directly with N3
it would take 31,709.8 years! Thus, someone who has to choose between
one of several algorithms for performing a task will (or should) be very concerned about the order of the
execution time functions of the algorithms.
One way to clasasify the complexity of an algorithm involves "big oh" notation: The function f is said to
be "big oh" of the function g, and we write f  O(g), or f g, if
lim
x
f(x)
g(x)
is a finite real constant. (1)
Thus, for example,
x2
 O(x3
) since lim
x
x2
x3
= 0.
And
x x lg x x2
x3
.
Note that L'Hopital's Rule is very useful in computing limits such as (1)!
Task
1. Show that if m  n then xm
xn
.
2. Show that, for every function f = f(x),
a) f f,
b) f kf for every non-zero positive constant k, and
c) kf f for every non-zero positive constant k.
3. Show that if f g and g h then f h.
4. Show that f(x) < g(x) for all x > N for some real number N, implies that f g, but that f g does
not imply that f(x) < g(x) for all x > N for some real number N.
5. List the functions below from lowest to highest order. If two (or more) are of the same order, indicate
this.
x x2
x3
4x3
+ 3x2
+ 2x
2x
ex
2x-1
xx
ln x lg x x2
+ lg x (lg x)2
lg lg x x lg x

x xx
+ 2x
Comments
There are other ways to classify the behavior of a function f = f(x) relative to another function g = g(x)
for large values of x. For example, some work uses f  (g) if
lim
x
f(x)
g(x)
is a finite non-zero real constant
while other work uses f  (g) if
lim
x
g(x)
f(x)
is a finite real constant.
On the other hand, there are also many ways to classify the behavior of a function f = f(x) relative to
another function g = g(x) for large values of x (|x| < for some > 0). For example, in writing
ex
= 1 + x + O(x2
)
we are saying that ex
can be written as 1 + x plus a function that can be written as x2
h(x) where h(x) is
continuous in a neighborhood of x = 0. More generally, f  O(g) if
lim
x0
f(x)
g(x)
is a finite real constant. (2)
Note that while the same notation O(g) is used for both (1) and (2), (1) and (2) actually define different
classes of functions. (The fact that the notation is the same is an unfortunate conflict in usage.) For example,
if f(x) = x2
and g(x) = x3
then f  O(g) using (1) but f  O(g) using (2), and g  O(f) using (2) but
g  O(f) using (1).