Path: csiph.com!news.swapon.de!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.programming Subject: Re: on reading ``o(1)'' Date: Sun, 26 Mar 2017 22:11:29 +0100 Organization: A noiseless patient Spider Lines: 45 Message-ID: <871stj7nge.fsf@bsb.me.uk> References: <86vaqydwqx.fsf@toledo.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx02.eternal-september.org; posting-host="ab227c206c7191e0d67e255dbc431e16"; logging-data="31497"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18w/4gDzNyRDCjMTcfRuHmhgfHCGxi3SOw=" Cancel-Lock: sha1:7/AAg+rCUxUxjNVyt9Ksjc3pkc4= sha1:LCIG6h/gv/ISpbDITiU0+xV+48Y= X-BSB-Auth: 1.d8bb660ebd4cb3737bc4.20170326221129BST.871stj7nge.fsf@bsb.me.uk Xref: csiph.com comp.programming:7643 Daniel Bastos writes: > Suppose f in o(1). By definition, there's a natural number n(0) such > that for any c > 0 > > 0 <= f < c * 1 = c > > for any n >= n(0). (AFAIK, c is a real number.) That seems to imply > that f = 0 because that's the only thing that could be less than any > c > 0. Not exactly. First, I would not write n(0) so it looks like a function. Call it n0 or make up a new name for it, M, say. Second, I would write f like a function (because it is one!). So, one definition of o(1) is that for any c > 0 there is a natural number M such that for all n > M, 0 <= f(n) < c. > So I thought saying f in o(1) would be useless, but searching for its > use I see mathematicians writing it out in apparently meaningful ways. Well, it's not entirely meaningless because it permits a (possibly very large) number of exception for "small n". So f being o(1) makes f approach 0 but f(10000) could be 10^700. > As for example in ``[t]he most obvious method to find small prime > divisors of n is trial division: divide n by 2, 3, 5, etc. This takes > time y^{1 + o(1)} if n has y^o(1) bits.''[1] > > I don't believe he meant ``if n has y^0 bits''. So how should I > read ``o(1)''? I must say I could not follow this quote at all, but since the paper is about problems with a fixed size to one of the components (finding the "small" prime divisors for some definition of "small", for example) it is not unlikely that o(1) might crop up. You can't say the cost is actually zero, but it is only non-zero for a finite number of cases. I'm sorry I can't be less vague. > [1] How to find small factors of integers. D.J. Bernstein, 2002. > URL: https://cr.yp.to/papers/sf.pdf -- Ben.