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

Groups > comp.programming > #7633 > unrolled thread

on reading ``o(1)''

Back to article view | Back to comp.programming

Contents

  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

#7633 — on reading ``o(1)''

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

[toc] | [next] | [standalone]

#7636

On 2017-03-25, Daniel Bastos <dbastos@toledo.com> wrote:
> Suppose f in o(1).  By definition, there's a natural number n(0) such
         ^^^^^^^^^^

(So indeed, we regard "o(1)" as denoting a set, in which f is found or
not.)

[toc] | [prev] | [next] | [standalone]

#7637

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

I believe there are two problems.  The first is that you are writing
`o(1)', but the paper is using `O(1)'. The two are rather different,
and I think you want to be talking about O(1).

The second is that your definition seems to have misplaced a
quantifier. The definition I know is that:

    f:R -> R is in O(1) if there exists a real number c and a real
    number N such that, for all n > N, |f(n)| < |c * 1| = |c|.

So f could be quite different from the zero function.  The classic
example is to let f(x) = sin(x).  Then you could take N = 0, c =
1.1, or perhaps N = 999, c = 999, etc.  However, f could not be
something like f(x) = x, or even f(x) = log(log(log(x))).

[toc] | [prev] | [next] | [standalone]

#7644

Michael Forsythe <forsythe@example.com> writes:

> Daniel Bastos <dbastos@toledo.com> wrote:
>> 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. 
>
> I believe there are two problems.  The first is that you are writing
> `o(1)', but the paper is using `O(1)'. The two are rather different,
> and I think you want to be talking about O(1).

The paper appears to use both, and the OP's quote from the paper has
what appears to be a very clear small o (and the paper is littered with
them).

> The second is that your definition seems to have misplaced a
> quantifier.

Not if, as I think is the case, the OP meant to define little-o(1).

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#7660

Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> Michael Forsythe <forsythe@example.com> writes:
> 
>> Daniel Bastos <dbastos@toledo.com> wrote:
>>> 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. 
>>
>> I believe there are two problems.  The first is that you are writing
>> `o(1)', but the paper is using `O(1)'. The two are rather different,
>> and I think you want to be talking about O(1).
> 
> The paper appears to use both, and the OP's quote from the paper has
> what appears to be a very clear small o (and the paper is littered with
> them).

Indeed - I should have squinted a bit harder. Thank you for correcting
me.

<snip>

[toc] | [prev] | [next] | [standalone]

#7661

Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> Michael Forsythe <forsythe@example.com> writes:
> 
>> Daniel Bastos <dbastos@toledo.com> wrote:
>>> 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. 
>>
>> I believe there are two problems.  The first is that you are writing
>> `o(1)', but the paper is using `O(1)'. The two are rather different,
>> and I think you want to be talking about O(1).
> 
> The paper appears to use both, and the OP's quote from the paper has
> what appears to be a very clear small o (and the paper is littered with
> them).

Indeed - I should have squinted a bit harder. Thank you for correcting
me.

[toc] | [prev] | [next] | [standalone]

#7643

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.

[toc] | [prev] | [next] | [standalone]

#7671

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

[toc] | [prev] | [next] | [standalone]

#7675

Daniel Bastos <dbastos@toledo.com> writes:

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

I respectfully disagree.  By all means make n a function but make it a
function of something useful.  As you use the notation, it is a
single-point function.  What are n(1), n(-e)?  What value does making it
a function have when there is only one point in the co-domain?

Secondly (and this is more important) you use n as not a function at the
very same time:  "for any n >= n(0)".  Now it's possible to unravel
that but, formally, the quantifier binds n in both locations.  At the
very least, use two names:  "there is an m(0) such that for all n >=
m(0) ...".

And to return to the first point, if you want to make it a function,
make it a useful one.  The n0 in question depends on c so make it a
function of c:

  For any c > 0 there is a natural number n(c) such that, for all k >=
  n(c), 0 <= f(k) < ck.

<snip>
> I picked this notation up with Brian M. Scott, an admirable
> mathematician who used to hang out at alt.algebra.help.

I strongly suspect he'd agree on this.  Making things into functions is
a great idea (and too few mathematician do it, relying instead on
subscripts and context to make it clear that this or that quantity is
linked to some other) but n is not a function when writing "for all n >
..." whatever goes in the ...

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#7686

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

> Daniel Bastos <dbastos@toledo.com> writes:
>
>> 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. :-)
>
> I respectfully disagree.  By all means make n a function but make it a
> function of something useful.  As you use the notation, it is a
> single-point function.  What are n(1), n(-e)?  

These are not defined at this point.  There are various ways to define a
function.  I can define a function by giving you a table of values.
Such function is defined on those values and nowhere else.  

> What value does making it a function have when there is only one point
> in the co-domain?

Well, one value is in using it as USENET notation. :-)

> Secondly (and this is more important) you use n as not a function at the
> very same time:  "for any n >= n(0)".  Now it's possible to unravel
> that but, formally, the quantifier binds n in both locations.  At the
> very least, use two names:  "there is an m(0) such that for all n >=
> m(0) ...".

I think you're correct here, but you're being pedantic, as a professor
of mine would put it.  Speaking of him, let tell you a little story.

One time I called this professor of mine's attention because he was
writing f^-1 to mean the preimage of some set element.  I remarked that
our textbook was wisely using a notation such as f^-| --- imagine a
little symbol that looks like a T rotated 90 degress clockwise.  The
author himself commented that that notation was to distinguish preimages
from inverse functions.

Looking back now in retrospective, I agree with my professor, without
disagreeing with the textbook author.  He explained that being pedantic
is fine, but it's also kind of pointless when you're talking to people
who understand what you're saying.  His words were something like this.
``If you don't know what's going on, it doesn't quite matter how I'm
saying.  You don't understand it anyway.  If you do know what's going
on, then there's no problem in reusing notation because you know what I
mean anyhow.''

I think he's right.  Obviously, if you write f^-1(a) and someone gets
confused or something, asks what you mean, then you can just explain
it's not the value of applying the inverse function of f on a, but
rather the subset of the domain of f for which any element is mapped to
a --- when f is applied to it.

Brian M. Scott himself would actually make a distinction between
preimage and inverse functions.  For preimages, he'd write f^-1[a],
saving f^-1(a) for the inverse function.

My professor would write f^-1(a) for both.

I think I'd go with Brian M. Scott, but I certainly wouldn't call my
professor's attention again.  Because he's right.

(*) Back to ``n''

When n is a dummy variable, I think anything is fine, even overloading n
--- because it's clear that while n(0) is a fixed object, n is a dummy
variable.  I wouldn't write for all n > n.  But I think n > n(0) is
unambiguous.  I agree this might confuse some people.  If it does, I'll
change it right away.  When it does not, I could go back to it.  I can
go back and forth.  (For instance, I can switch languages speaking to a
foreigner, if I can speak his language.)

> And to return to the first point, if you want to make it a function,
> make it a useful one.  The n0 in question depends on c so make it a
> function of c:
>
>   For any c > 0 there is a natural number n(c) such that, for all k >=
>   n(c), 0 <= f(k) < ck.

Here you're perfectly correct.  This is really how it should be.  That
does inform the reader.  It's what I do when I write epsilon-delta
proofs, because a delta is usually dependent on the epsilon.  (And that
I picked up with Paul Sperry.)

Of course, if I use two constants there, I'd have to write n(c,0) and
then n(c, 1).  To me that's fine.

> <snip>
>> I picked this notation up with Brian M. Scott, an admirable
>> mathematician who used to hang out at alt.algebra.help.
>
> I strongly suspect he'd agree on this.  Making things into functions is
> a great idea (and too few mathematician do it, relying instead on
> subscripts and context to make it clear that this or that quantity is
> linked to some other) but n is not a function when writing "for all n >
> ..." whatever goes in the ...

After Brian M. Scott, when I look at subscripts now in texts, what I
actually imagine is a function with the subscript being its argument. :-)

I think this is about communication.  My way exchanging information is
to adapt myself to whom I'm speaking to.

Thank you!

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web