Re: Big-O notation, multiple variables

Googmeister wrote:
On Jun 21, 12:13 pm, Rod Howell <rhow...@xxxxxxx> wrote:
deepakc wrote:
On 21 Jun, 10:46, deepakc <deep...@xxxxxxxxxxxxxxxx> wrote:
On 19 Jun, 21:04, Rod Howell <rhow...@xxxxxxx> wrote:
I'm looking for pointers to any discussion in the literature regarding
the pitfalls involved in extending Big-O notation to multiple variables.
It's been hard enough just to find a formal definition, as most authors
define it only for 1 variable, even if they want to use it for multiple
variables. However, the problems involved in extending the notation to
multiple variables are severe enough that it would seem that the issue
would have been treated somewhere in the literature. I'd also be
interested in seeing any treatments comparing alternative definitions.
Thanks in advance,
Rod Howell
Associate Professor
Dept. of Computing and Information Sciences
Kansas State University
....

Sorry for being naive, but to what severe issue are you referring?
What are the alternate definitions?

The definition that appears to be the most common is as follows (stated for 2 variables for simplicity):

O(f(m,n)) is the set of all functions g(m,n) such that there exist a positive real number c and a natural number n_0 such that g(m,n) <= cf(m,n) whenever both m >= n_0 and n >= n_0.

I'm assuming that all functions under consideration map pairs of natural numbers into the nonnegative real numbers. One alternative definition that I have seen (though I can't find any references for it now) is to replace "both m >= n_0 and n >= n_0" with "either m >= n_0 or n >= n_0".

The problems that I mention are those in which properties of single-variable big-O notation don't extend to more than one variables. Some of these properties are routinely assumed by people analyzing algorithms with more than one natural parameter. For example, using the second definition above, mn + 1 is not in O(mn) because mn is 0 infinitely often, whereas mn + 1 is always strictly positive. This is relevant for algorithm analysis because all algorithms require some nonzero time on every input; hence, using this definition, there can be no algorithms with running time in O(mn). Similar (though different) problems exist with the first definition; however, I've been unable to find any paper discussing these problems.

I'm working on a paper in which I examine these problems and propose a solution. I hope to have a draft soon, and I can post a link to it at that time. In the meantime, I'd be interested in knowing if anyone else has written about such problems. I'd like to give proper credit to them as well as perhaps to gain more insight into the problems.

Rod
.

Relevant Pages

  • Re: Big-O notation, multiple variables
    ... the pitfalls involved in extending Big-O notation to multiple variables. ... algorithms with more than one natural parameter. ...
    (comp.theory)
  • Re: Big-O notation, multiple variables
    ... the pitfalls involved in extending Big-O notation to multiple variables. ... algorithms with more than one natural parameter. ... Suppose we know that the running time of Gis in O. ...
    (comp.theory)
  • Re: Big-O notation, multiple variables
    ... the pitfalls involved in extending Big-O notation to multiple variables. ... It's been hard enough just to find a formal definition, ...
    (comp.theory)