From: David Eppstein <eppstein@ics.uci.edu>

Date: Wed, 12 Apr 2000 09:45:38 -0700

To: www-math@w3.org

cc: roconnor@uwaterloo.ca, jsdevitt@radicalflow.com

Message-ID: <12784318.3164521538@cx344290-c.irvn1.occa.home.com>

Date: Wed, 12 Apr 2000 09:45:38 -0700

To: www-math@w3.org

cc: roconnor@uwaterloo.ca, jsdevitt@radicalflow.com

Message-ID: <12784318.3164521538@cx344290-c.irvn1.occa.home.com>

"Russell Steven Shawn O'Connor" <roconnor@uwaterloo.ca> writes: > Are you saying that if an application wants to read the argueably > meaningless statement [f(x) = 5x + 6x^2 + O(x^3)], then it has to figure > out that it really means [f(x) - 5x - 6x^2 $isin; O(x^3)]. I suppose > that's fair. In what sense is the first statement meaningless? To me, it means that there exists a function g(x) and numbers c and x0, such that for all x>x0, g(x)<=cx^3, and such that f(x) = 5x + 6x^2 + g(x). So, the equality really is an equality, and the O is a convenient shorthand for "a function I don't want to bother naming, that has certain asymptotic growth behavior". I think it is incorrect to say that the two statements are the same or that the first one "really means" the second. For instance, I would hope that a symbolic algebra system might know enough to simplify the first expression to f(x)=O(x^3) since the other two terms on the rhs have lower growth rates, while the second expression should not be simplified. If you want to argue about sloppy definitions wrt O-notation, a much worse problem is specifying which parameters are variable and which are constant, i.e. if we think of statements like the one above about f(x) as being implicitly quantified with "for all x", the question is whether these universal quantifiers go before or after the existential quantifiers on c and x0. For instance, in my research area (computational geometry) it is common in problems concerning say sets of n points in R^d to treat n as variable and d as constant so that time bounds like 2^{2^d}n become O(n). Explicitly representing this seems more problematic than simply introducing O-notation -- normally one simply states assumptions like this somewhere in the text of a paper -- but perhaps one could have some kind of type=... attribute on the <ci>d</ci>. Speaking of which, is there any way of making <declare> act only within a certain scope rather than an entire document? -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/Received on Wednesday, 12 April 2000 12:45:40 GMT

*
This archive was generated by hypermail 2.2.0+W3C-0.50
: Saturday, 20 February 2010 06:12:49 GMT
*