Re: Big-O notation, multiple variables

On Jun 22, 3:13 pm, Googmeister <googmeis...@xxxxxxxxx> wrote:
On Jun 22, 12:32 pm, Rod Howell <rhow...@xxxxxxx> wrote:



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).

This probably explains why this alternate definition is seldom used.

Similar (though different)

problems exist with the first definition; however, I've been unable to
find any paper discussing these problems.

What are the problems with the standard definition?

Consider the following algorithm, assuming m and n are natural
numbers:

F(m,n) {
for (i <- 0 to m) {
G(i,n)
}
}

Suppose we know that the running time of G(i,n) is in O(in). I think
nearly everyone would conclude that the running time of F(m,n) is then
in O(m^2 n). However, using the standard definition of big-O on 2
variables, this does not necessarily hold. In fact, we don't have
enough information to give any upper bound on the running time of
F(m,n).

For example, suppose G(i,n) is defined as follows:

G(i,n) {
if (i = 0) {
H(n)
}
else {
for (j <- 1 to i) {
for (k <- 1 to n) {}
}
}
}

With the standard definition of O on 2 variables, we don't need to
know the running time of H(n) in order to analyze G(i,n) because H is
only called when i = 0. The running time of G(i,n) is therefore in
O(in), as we have assumed above. However, the running time of H(n)
does impact the running time of F(m,n) because H is called once for
any values of m and n. Thus, if the running time of H(n) is in
O(h(n)), the running time of F(m,n) is in O(h(n) + m^2 n). If h(n) is
not in O(n), then the running time of F(m,n) is not in O(m^2 n). In
fact, without knowing anything about h(n), we cannot derive any upper
bound on the running time of F(m,n).

Has anyone seen any discussion of this kind of problem?

Rod

.

Relevant Pages

  • Re: Factoring program
    ... >> Proper analysis of the algorithms is not done by collecting data points. ... Understanding the running time takes a little more effort, ... outside of your extrapolation range, you will have to use the real running ... The running time of quadratic sieve is: ...
    (sci.crypt)
  • The Running Time of += on Char Strings ?
    ... What is the running time of conactination on character strings. ... I can't think of an instance where it would be appropriate to specify ... > runtime properties of various algorithms in the language. ... data structures are choosen with the size/speed tradeoffs in mind. ...
    (comp.lang.python)
  • Re: zip() function troubles
    ... algorithms. ... The environment may affect the running time by an additive or linear ... multiplicative constant but it should never turn an Oalgorithm ...
    (comp.lang.python)
  • Re: Breaking Large Composite Numbers...???
    ... The Travelling Sales person problem has practical limitations in ... TSP is NP-Hard. ... Because algorithms like the ... sieve running time to the running time of the algorithm that ...
    (sci.crypt)
  • 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)