[Prev][Next][Index][Thread]
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
References: