Asymptotic notation, multiple variables

Last June I posted an announcement of my paper, "On Asymptotic
Notation with Multiple Variables." In this paper I showed that several
of the commonly-used properties of big-O notation are inconsistent
when applied to functions on more than one variable. I then proposed a
new definition that (I claimed) implies these properties when the
functions within the asymptotic notation are restricted to being
strictly nondecreasing. However, I've recently discovered a fatal flaw
in this definition, so that these properties don't all hold.

I have now revised the paper using a different definition. (I had
actually considered this definition last summer, but rejected it for
reasons I can no longer recall.) The new definition is actually
simpler and yields much simpler proofs than the original. The revised
paper can be found at

For those of you who may have the original paper and are curious what
the error was, Theorems 3.8 and 3.9 are invalid. (I'm using the
theorem numbers from a revision dated August 29, 2007 - I don't have a
copy of the version originally posted, but I think the theorem numbers
are the same.) A counter-example for both theorems consists of the
functions f(m, n) = mn and g(m, n) defined to be:

- m^2 for m a power of 2 and n = 0;
- mn otherwise.

No proof is given for Theorem 3.8 - I instead claim that it is not
hard to show (oops). The error in the proof of Theorem 3.9 is that c'
depends on n_1, ..., n_{k-1}.

Rod Howell
Associate Professor
Dept. of Computing and Information Sciences
Kansas State University