Re: standard usage of O(x^3) can be confusing

"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 UTC