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

On Wed, 12 Apr 2000, David Eppstein wrote:

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

That is also a valid definition of the meaning of (1), but note that in
both your case and in my case we hand to translate the statement into
something else.  I rearranged stuff and used set inclusion.  Your
rearranged a bit less, but added two quantifiers.  Either way the point is
that if the statement is going to get used by a computer, it is going to
have to get translated into a first-order statement.  In that sense (1) is
meaningless because it is not a first-order statement.

That is why I was concerned, but now I get the impression that it is up to
whatever UA to perform the translation from (1) into a meaningful FO
statement.

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

why not.  f(x) = O(x^3) iff f(x) - 5x - 6x^2 = O(x^3).  It seems fair to
simplify the second expression if interpreting it.
 
> If you want to argue about sloppy definitions wrt O-notation,

[Good example...]

Okay this brings up a very good point.  This is how I see the world.

O(f(x)) is either a subset of functions from R to R, or perhaps in yoru
quantifier case g(x) must be a function from R to R (otherwise the
comparison g(x) <= c*x^3 makes no sense).

If f is a function from R^2 to R, then one can't apply the normal
definition.  Once has to curry f, and make a new function F(d)(x) (often
writeens as F<sub>d</sub>(x) ), where F is a function from R to the set of
function from R to R. 

Since currying wrt the first variable is different from currying wrt the
second variable, one can't determine how to curry without the authours
help.

So MathML needs a curry object.  But you might feel (and so do I) that a
currly function makes MathML to complex.  Currying isn't really taught in
K-13.  But I don't see how one can actually encode spemantics without
getting your hands dirty like this.

-- 
Russell O'Connor                           roconnor@uwaterloo.ca
       <http://www.undergrad.math.uwaterloo.ca/~roconnor/>
``Paradoxically, a refusal to `put a monetary value on life' means that
life is often undervalued.'' -- Artificial Intelligence: A Modern Approach

Received on Wednesday, 12 April 2000 13:18:48 UTC