Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #7643

Re: on reading ``o(1)''

Show all headers | View raw

Daniel Bastos <dbastos@toledo.com> 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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

on reading ``o(1)'' Daniel Bastos <dbastos@toledo.com> - 2017-03-24 21:29 -0300
  Re: on reading ``o(1)'' Kaz Kylheku <336-986-7787@kylheku.com> - 2017-03-25 02:40 +0000
  Re: on reading ``o(1)'' Michael Forsythe <forsythe@example.com> - 2017-03-25 05:51 +0000
    Re: on reading ``o(1)'' Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-26 22:14 +0100
      Re: on reading ``o(1)'' Michael Forsythe <forsythe@example.com> - 2017-03-28 10:32 +0000
      Re: on reading ``o(1)'' Michael Forsythe <forsythe@example.com> - 2017-03-28 10:33 +0000
  Re: on reading ``o(1)'' Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-26 22:11 +0100
    Re: on reading ``o(1)'' Daniel Bastos <dbastos@toledo.com> - 2017-03-28 21:05 -0300
      Re: on reading ``o(1)'' Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-29 14:23 +0100
        Re: on reading ``o(1)'' Daniel Bastos <dbastos@toledo.com> - 2017-04-03 09:40 -0300

csiph-web