Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: on reading ``o(1)'' Date: Fri, 24 Mar 2017 21:29:42 -0300 Organization: Aioe.org NNTP Server Lines: 23 Message-ID: <86vaqydwqx.fsf@toledo.com> NNTP-Posting-Host: BuEqJTf8bEmpZhBIUMG+Zw.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain X-Complaints-To: abuse@aioe.org User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt) Cancel-Lock: sha1:kO92pliMlrkv4W4uhSrMbJwrJzo= X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:7633 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. 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. 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)''? Thank you. [1] How to find small factors of integers. D.J. Bernstein, 2002. URL: https://cr.yp.to/papers/sf.pdf