[Prev][Next][Index][Thread]
Re: standard usage of O(x^3) can be confusing
"Russell Steven Shawn O'Connor" <roconnor@uwaterloo.ca> writes:
> 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.
Bogus argument. The whole point of any notation is as a shorthand for
something else. Plenty of other notations need translation to become
first order e.g.
lim_{x->0} (sin x / x) = 1
"really means"
Exists(L) all(epsilon>0) exists(delta>0) all(x:|x|<=delta)
|(sin x / x) - L| <= epsilon,
and furthermore L=1.
People don't usually do this sort of explicit translation whenever they
manipulate limits or O's, why do you think a computer should have to? For
instance, in Mathematica or other symbolic symbols, it would be perfectly
straightforward to add a simplification rule that O(x^i)+p(x) simplifies
to O(x^i) whenever p is a polynomial with degree at most i. Such a rule
doesn't require any deeper understanding of what O "really means".
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Follow-Ups:
References: