Re: Big-O notation, multiple variables

A draft of my paper entitled, "On Asymptotic Notation with Multiple Variables", can be found at

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

The abstract is as follows:

We show that it is impossible to define big-O notation for functions
on more than one variable in a way that implies the properties
commonly used in algorithm analysis. We also demonstrate that common
definitions do not imply these properties even if the functions within
the big-O notation are restricted to being strictly nondecreasing. We
then propose an alternative definition that does imply these properties
whenever the function within the big-O notation is strictly
nondecreasing.


The draft is still pretty rough, but I'm not going to be able to work on it for the next month, and I wanted to get something posted before then. I plan to add some material on recurrences and more details on other asymptotic notation (i.e., big-Omega, etc.). I'm thinking of submitting it to STACS, which has a mid-September deadline. In the meantime, feedback is welcome.

Rod
.

Relevant Pages

  • Re: Prolog portability quest 1
    ... Jan Burse writes: ... is the reason: In both the argument list of functional ... notation and the elements of a list you have ... a draft) has in effect the same problem: ...
    (comp.lang.prolog)
  • Asymptotic notation, multiple variables
    ... Notation with Multiple Variables." ... of the commonly-used properties of big-O notation are inconsistent ... For those of you who may have the original paper and are curious what ...
    (comp.theory)