Re: Big-O notation, multiple variables
- From: tchow@xxxxxxxxxxxxx
- Date: 22 Jun 2007 20:24:33 GMT
In article <f5gt0v$nre$1@xxxxxxxxxxxxxxx>, Rod Howell <rhowell@xxxxxxx> wrote:
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.
Section 25.7 of "Modern Computer Algebra," 2nd ed., by Joachim von zur
Gathen and Juergen Gerhard (Cambridge University Press, 2003) says:
We often also use the O-notation for functions g of two or three
arguments, in the following sense. A partial function g:NxN->R is
eventually positive if there is a constant n_0 in N such that g(m,n)
is defined and positive for all m, n >= n_0. For such a function g,
O(g) is the set of all eventually positive functions f:NxN->R for
which there exist n_0, c in N such that f(m,n) and g(m,n) are
defined and f(m,n) <= c g(m,n) for all m, n >= n_0, and similarly
for ternary functions.
[Actually, they use a blackboard bold "N" where I've written simply N,
and they write an uppercase N where I've written n_0.]
They also refer the reader to Chapter 3 of "Fundamentals of Algorithmics,"
by Gilles Brassard and Paul Bratley (Prentice-Hall, 1996). I don't have
ready access to this book, but Amazon.com has the table of contents, and
Section 3.5 is titled, "Asymptotic notation with several parameters."
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.
- Follow-Ups:
- Re: Big-O notation, multiple variables
- From: Rod Howell
- Re: Big-O notation, multiple variables
- References:
- Big-O notation, multiple variables
- From: Rod Howell
- Re: Big-O notation, multiple variables
- From: Rod Howell
- Re: Big-O notation, multiple variables
- From: Googmeister
- Re: Big-O notation, multiple variables
- From: Rod Howell
- Big-O notation, multiple variables
- Prev by Date: Re: Big-O notation, multiple variables
- Next by Date: Re: A letter want to disprove my paper which submitted recently
- Previous by thread: Re: Big-O notation, multiple variables
- Next by thread: Re: Big-O notation, multiple variables
- Index(es):
Relevant Pages
|
