[Prev][Next][Index][Thread]
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/
Follow-Ups: