Big O: 2 Functions Map from N to N+

From: Scott Turner
Date: Sat, 22 Jun 1996 13:39:17 -0400 (EDT)
Subject: The Big O

True or False:  Let f, g: N ->  N+, then either f(x) is O(g(x)) or
g(x) is O(f(x)).  Why?

Date: Mon, 24 Jun 1996 14:17:53 -0400 (EDT)
From: "Dr. Math"
Subject: Re: The Big O

Maybe I don't understand the question, since I don't know what
you mean by "N+".  If it just means positive integers, then
your statement is false:

f(odd number n) = 1
f(even number n) = 2^n
g(odd number n) = 2^n
g(even number n) = 1

But maybe "f, g: N -> N+" means increasing functions or
something.

Please clarify.

-Doctor Tom,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: Tue, 25 Jun 1996 09:53:01 -0400 (EDT)
From: Scott Turner
Subject: Re: The Big O

I do mean positive integers by N+ but don't understand your 
explanation.

If two functions map from N to N+, I picture two graphs in the upper 
right quadrant and it seems that if the two graphs are equal then they 
are O to each other, if they aren't equal, one is big O of the other?

Thanks.  ST

Date: Tue, 25 Jun 1996 16:56:49 -0400 (EDT)
From: "Dr. Math"
Subject: Re: The Big O

The "O" or "big-O" notation is usually used to compare rates of growth
of functions.  It's used to compare what happens "in the long run",
usually for functions that are both increasing, but at different
rates.  For applications like computer science, they are used to
compare algorithm performance.  For example, if you have two
sorting schemes, one of which takes 1000*n*log(n) cycles to do
the sort and another of which takes n^2 cycles, for sorting small
numbers of items, the n^2 sort is better.  In the long run, for
giant sorts, the 1000*n*log(n) algorithm is better, and it's
better for ALL sorting problems above a certain size.

But arbitrary functions that can go up and down may not be
comparable.  Sometimes one is bigger and sometimes the other.
The example I gave shows two functions that alternate which one
is bigger forever, and not only that, but the relative size of
each against the other at alternate points also grows without
bound.

Just because you can write down a definiton of a relationship
between 2 mathematical things that sounds sort of like a comparison
relationship doesn't mean that any two things can be compared.

O is a comparison operator, and for some functions f and g we
can say that f = O(g) or vice-versa.  But there exist f and g
(as in my example - and there are an infinite number of other
examples) where neither f = O(g) or g = O(f) holds. 


-Doctor Tom,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/