Re: Big-O notation, multiple variables

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

I have not found literature in that regard too, and so this is a
unique Question. It is good u brought this up this Question. In my
opinion, it is alright to go ahead to use Big-O notation for multiple
variables as long as u are sure that those are independent variables
(i.e. one of those variables cannot be expressed as a function of the
other variables).

.

Relevant Pages

  • 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)
  • 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)
  • Re: Big-O notation, multiple variables
    ... the pitfalls involved in extending Big-O notation to multiple variables. ... The problems that I mention are those in which properties of single-variable big-O notation don't extend to more than one variables. ... 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. ...
    (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. ...
    (comp.theory)
  • Big-O notation, multiple variables
    ... 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. ... 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. ...
    (comp.theory)