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

Groups > comp.programming > #7671

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

Show all headers | View raw

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> 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.

This notation is great!  Let me defend it.  Consider n as a function
that takes an argument 0 and gives you the constant ``n0'' --- as you
like to write.  Functions can give anything you prefers to read. :-)

Suppose now that you want n_{0_y} --- using TeX notation.  Look how
horrible this notation is for USENET.  Much better to write n(0,y)
because it already says n is dependent on 0 and y and you can just
imagine the function n giving you any symbol you'd prefer to see.

I picked this notation up with Brian M. Scott, an admirable
mathematician who used to hang out at alt.algebra.help.  I'd like to
take this opportunity to leave here my sincere thanks to him.  For
years, he scrutinized my arguments and carefully explained a lot of
difficult mathematics (to me).  None of my university professors could
ever give me all that attention.  (Another who did the same was Paul
Sperry.  I think sometimes they'd distribute my threads among the two of
them.)

While we're here, thank you too.  It's not the first time you clarify a
lot of the trouble I go through with mathematics.  Thank you.
(Obviously I'm grateful to everyone who contributes.  For example, Kaz
Kylheku.)

> 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!). 

Here I agree.  It's just that sometimes I get lazy, but I prefer f(n)
too.  Sometimes the n is there for really nothing.  So when it's very
clear...  But I were not the one typing, I'd put it there. :-)

>> 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.

I think I see.  f is asymptotically zero (if I may say it that way), but
it can vary wildly while n is still ``small''.

>> 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.

No need to sorry about that.  Thank you.

>> [1] How to find small factors of integers.  D.J. Bernstein, 2002.
>> URL: https://cr.yp.to/papers/sf.pdf

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