# Asymptotic notation, multiple variables

*From*: Rod Howell <rhowell@xxxxxxx>*Date*: Fri, 18 Jan 2008 12:43:25 -0800 (PST)

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 http://people.cis.ksu.edu/~rhowell/asymptotic.pdf

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

http://people.cis.ksu.edu/~rhowell/

.

- Prev by Date:
**Re: Could anyone help me with this math problem please?** - Next by Date:
**CALL FOR PAPERS: Finite-State Methods and Natural Language Processing 2008** - Previous by thread:
**Could anyone help me with this math problem please?** - Next by thread:
**CALL FOR PAPERS: Finite-State Methods and Natural Language Processing 2008** - Index(es):