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

Groups > comp.lang.javascript > #32657 > unrolled thread

Update only if not already in array

Back to article view | Back to comp.lang.javascript

Contents

  Update only if not already in array jonas.thornvall@gmail.com - 2017-03-01 05:36 -0800
    Re: Update only if not already in array Julio Di Egidio <julio@diegidio.name> - 2017-03-01 05:53 -0800
      Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-01 07:29 -0800
        Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-01 12:04 -0800
          Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 02:27 -0800
            Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-03 13:02 +0100
              Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 09:07 -0800
                Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 09:13 -0800
                Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-03 18:20 +0100
                  Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 14:30 -0800
                    Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-03 23:41 +0100
                      Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 14:48 -0800
                      Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 14:52 -0800
                        Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-04 00:07 +0100
                          Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 16:00 -0800
                            Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-04 12:35 +0100
                              Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-04 06:00 -0800
                                Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-04 15:24 +0100
                            Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-04 07:02 -0800
                              Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-04 15:51 +0000
                                Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-04 09:57 -0800
                                  Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-04 20:56 +0000
                                    Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-04 15:30 -0800
                                      Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-04 15:37 -0800
                                        Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-05 00:41 +0000
                                      Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-05 00:29 +0000
                                        Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-05 06:26 -0800
                                          Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-05 15:00 +0000
                                            Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-06 07:50 -0800
                                              Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 00:50 +0000
                                                Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 06:46 +0100
                                                  Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 11:23 +0000
                                                    Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 15:34 +0100
                                                      Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 16:47 +0000
                                                        Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 17:55 +0100
                                                          Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 17:28 +0000
                                                            Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 21:07 +0100
                                                              Re: Update only if not already in array Flippie Flink <flip@flink.not> - 2017-03-07 22:29 +0100
                                                Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-11 18:24 -0800
                                                  Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-15 17:32 +0000
                                                    Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-15 10:59 -0700
                                                      Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-16 03:49 +0000
                                                        Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-18 11:46 -0700
                                                          Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-18 20:12 +0000
                                                            Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-18 20:45 +0000
                                                            Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-26 11:54 -0700
                                                              Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-27 22:48 +0100
    Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-01 15:32 +0100

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#32679

Ben Bacarisse wrote:

> NP-hard is precisely defined, but would you say that when someone talks
> about a hard problem they always mean NP-hard?  I suppose that's the
> natural thing to assume when talking about complexity but I wouldn't be
> certain.  It still carries a strong informal meaning.

Of course in general conversation, no. Nor in general conversation about programming. Most programmers and developers have no formal education and therefore carry their own bias with their terminology. Confusion is caused when the same word is used with different meanings by people in the same topic being discussed and should be avoided. When Jonas moved from informal conversation to criticism regarding factorization he moved into a field where the terminology is is not so informal.

In most writings IME, a "small" problem is computable in polynomial time (such as n^3). Whereas a "large" problem would be computable in exponential time (such as 2^n). For example: 

If I had two functions, each with a respective running time of the above:

// O(n^3)
function small(n){ ... }

// O(2^n)
function big(n){ ... }

small(1000) // 1 billion steps to complete
big(1000) // 1 x 10^301 steps to complete

If you graphed n^3 and 2^n you can see the shape of the problem [1][2]

Faster computers simply shift the curve left, but don't change the shape of the graph.

> Anyway, if we take hard to mean NP-hard then integer factorisation is
> not know to be hard, and most people would say that they don't expect it
> to turn out to be.  The key new fact being that we now know that
> primality testing is in P which puts the decision problem version of
> factorisation in co-NP.

Factorization is considered "hard" or "difficult" presently [3] because you have to use brute force to search for possible solutions instead of deriving them directly from what was computed already

[1] <http://www.wolframalpha.com/input/?i=Plot%5Bn%5E3,+%7Bn,+0,+1000%7D%5D>
[2] <http://www.wolframalpha.com/input/?i=Plot%5B2%5En,+%7Bn,+0,+1000%7D%5D>
[3] Excluding some Quantum Computing algorithm which can do this theoretically in polynomial time, but have in reality only factored very small numbers <https://en.wikipedia.org/wiki/Integer_factorization_records#Records_for_efforts_by_quantum_computers>

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

#32681

"Michael Haufe (TNO)" <tno@thenewobjective.com> writes:

> Ben Bacarisse wrote:
>
>> NP-hard is precisely defined, but would you say that when someone talks
>> about a hard problem they always mean NP-hard?  I suppose that's the
>> natural thing to assume when talking about complexity but I wouldn't be
>> certain.  It still carries a strong informal meaning.
>
> Of course in general conversation, no. Nor in general conversation
> about programming. Most programmers and developers have no formal
> education and therefore carry their own bias with their
> terminology. Confusion is caused when the same word is used with
> different meanings by people in the same topic being discussed and
> should be avoided. When Jonas moved from informal conversation to
> criticism regarding factorization he moved into a field where the
> terminology is is not so informal.
>
> In most writings IME, a "small" problem is computable in polynomial
> time (such as n^3). Whereas a "large" problem would be computable in
> exponential time (such as 2^n).

That's interesting.  I've not come across that usage.  I would take the
terms small and large to refer to the quantity of data.

> For example:
>
> If I had two functions, each with a respective running time of the above:
>
> // O(n^3)
> function small(n){ ... }
>
> // O(2^n)
> function big(n){ ... }

I wanted to mention a pet peeve of mine, but I see from Wikipedia that
it's becoming accepted to use O(f) in this way.  But in case there is
some chance save the old meaning, I'll just say that when I leaned about
it, Big-O was only an (asymptotic) upper bound, so the function called
small is also O(2^n), and the one called big might be O(n^3).  (A lower
bound was given by Omega and both bounds by Theta.)

> small(1000) // 1 billion steps to complete
> big(1000) // 1 x 10^301 steps to complete

Or almost any other number of steps, surely?  The order of growth says
only that steps(small(2*x)) ~ 8*steps(small(x)).

<snip>
>> Anyway, if we take hard to mean NP-hard then integer factorisation is
>> not know to be hard, and most people would say that they don't expect it
>> to turn out to be.  The key new fact being that we now know that
>> primality testing is in P which puts the decision problem version of
>> factorisation in co-NP.
>
> Factorization is considered "hard" or "difficult" presently [3]
> because you have to use brute force to search for possible solutions
> instead of deriving them directly from what was computed already

That's probably how Jonas meant it, too.  Was your complaint that he
should have put "hard" in scare quotes rather than "thought"?  If so, I
misunderstood your original reply.  Sorry about that.

<snip>
-- 
Ben.

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

#32687

Ben Bacarisse wrote:
> "Michael Haufe (TNO)" writes:

> > In most writings IME, a "small" problem is computable in polynomial
> > time (such as n^3). Whereas a "large" problem would be computable in
> > exponential time (such as 2^n).
> 
> That's interesting.  I've not come across that usage.  I would take the
> terms small and large to refer to the quantity of data.

The amount of data in this sense would be the specific value of 'n'.

In the context of algorithms, I've also seen common use of "simple"/"complex" to refer to the same.

> > For example:
> >
> > If I had two functions, each with a respective running time of the above:
> >
> > // O(n^3)
> > function small(n){ ... }
> >
> > // O(2^n)
> > function big(n){ ... }
> 
> I wanted to mention a pet peeve of mine, but I see from Wikipedia that
> it's becoming accepted to use O(f) in this way.  But in case there is
> some chance save the old meaning, I'll just say that when I leaned about
> it, Big-O was only an (asymptotic) upper bound, so the function called
> small is also O(2^n), and the one called big might be O(n^3).  (A lower
> bound was given by Omega and both bounds by Theta.)

What you learned is still true. I'm abusing notation slightly which is sadly a bad habit I've picked up and is a bit common: 
<https://en.wikipedia.org/wiki/Big_O_notation#Matters_of_notation>

> > small(1000) // 1 billion steps to complete
> > big(1000) // 1 x 10^301 steps to complete
> 
> Or almost any other number of steps, surely?  The order of growth says
> only that steps(small(2*x)) ~ 8*steps(small(x)).

Any *fewer* number of steps, yes. Constant factors are irrelevant at scale and are ignored:

<https://en.wikipedia.org/wiki/Big_O_notation#Multiplication_by_a_constant>

> > Factorization is considered "hard" or "difficult" presently [3]
> > because you have to use brute force to search for possible solutions
> > instead of deriving them directly from what was computed already
> 
> That's probably how Jonas meant it, too.  Was your complaint that he
> should have put "hard" in scare quotes rather than "thought"?  If so, I
> misunderstood your original reply.  Sorry about that.

The way I read that statement "... 'thought' to be a hard problem ..." was that he disagreed that it was. My interpretation is admittedly colored by his other statements in this thread and other threads. I could also be hitting a language barrier here...

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

#32689

Den söndag 5 mars 2017 kl. 00:30:04 UTC+1 skrev Michael Haufe (TNO):
> Ben Bacarisse wrote:
> > "Michael Haufe (TNO)" writes:
> 
> > > In most writings IME, a "small" problem is computable in polynomial
> > > time (such as n^3). Whereas a "large" problem would be computable in
> > > exponential time (such as 2^n).
> > 
> > That's interesting.  I've not come across that usage.  I would take the
> > terms small and large to refer to the quantity of data.
> 
> The amount of data in this sense would be the specific value of 'n'.
> 
> In the context of algorithms, I've also seen common use of "simple"/"complex" to refer to the same.
> 
> > > For example:
> > >
> > > If I had two functions, each with a respective running time of the above:
> > >
> > > // O(n^3)
> > > function small(n){ ... }
> > >
> > > // O(2^n)
> > > function big(n){ ... }
> > 
> > I wanted to mention a pet peeve of mine, but I see from Wikipedia that
> > it's becoming accepted to use O(f) in this way.  But in case there is
> > some chance save the old meaning, I'll just say that when I leaned about
> > it, Big-O was only an (asymptotic) upper bound, so the function called
> > small is also O(2^n), and the one called big might be O(n^3).  (A lower
> > bound was given by Omega and both bounds by Theta.)
> 
> What you learned is still true. I'm abusing notation slightly which is sadly a bad habit I've picked up and is a bit common: 
> <https://en.wikipedia.org/wiki/Big_O_notation#Matters_of_notation>
> 
> > > small(1000) // 1 billion steps to complete
> > > big(1000) // 1 x 10^301 steps to complete
> > 
> > Or almost any other number of steps, surely?  The order of growth says
> > only that steps(small(2*x)) ~ 8*steps(small(x)).
> 
> Any *fewer* number of steps, yes. Constant factors are irrelevant at scale and are ignored:
> 
> <https://en.wikipedia.org/wiki/Big_O_notation#Multiplication_by_a_constant>
> 
> > > Factorization is considered "hard" or "difficult" presently [3]
> > > because you have to use brute force to search for possible solutions
> > > instead of deriving them directly from what was computed already
> > 
> > That's probably how Jonas meant it, too.  Was your complaint that he
> > should have put "hard" in scare quotes rather than "thought"?  If so, I
> > misunderstood your original reply.  Sorry about that.
> 
> The way I read that statement "... 'thought' to be a hard problem ..." was that he disagreed that it was. My interpretation is admittedly colored by his other statements in this thread and other threads. I could also be hitting a language barrier here...

Well thought suggest that people agree upon it is a hard problem, but there is no proof it actually is one. And if it indeed solved during a couple on a 16 Mhz computer it probably "it probably just thought to be a hard problem".

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

#32691

jonas.thornvall@gmail.com writes:

> Den söndag 5 mars 2017 kl. 00:30:04 UTC+1 skrev Michael Haufe (TNO):
>> Ben Bacarisse wrote:
<snip>
>> > That's probably how Jonas meant it, too.  Was your complaint that he
>> > should have put "hard" in scare quotes rather than "thought"?  If so, I
>> > misunderstood your original reply.  Sorry about that.
>> 
>> The way I read that statement "... 'thought' to be a hard problem
>> ..." was that he disagreed that it was. My interpretation is
>> admittedly colored by his other statements in this thread and other
>> threads. I could also be hitting a language barrier here...
>
> Well thought suggest that people agree upon it is a hard problem, but
> there is no proof it actually is one.

Which bit are you complaining about?  The complexity class of
factorisation was not known then and is not known today so all opinions
about it are just "thoughts" rather than proofs.  Do you object to the
fact that most well-informed people agreed on the notion that it appears
to be hard?  Everywhere but on Usenet that's often a sign that the
opinion is worth listening to.

> And if it indeed solved during a couple on a 16 Mhz computer it
> probably "it probably just thought to be a hard problem".

I've no idea what that means, but that's a language thing, I think.

-- 
Ben.

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

#32690

"Michael Haufe (TNO)" <tno@thenewobjective.com> writes:

> Ben Bacarisse wrote:
>> "Michael Haufe (TNO)" writes:
<snip>
>> > If I had two functions, each with a respective running time of the above:
>> >
>> > // O(n^3)
>> > function small(n){ ... }
>> >
>> > // O(2^n)
>> > function big(n){ ... }
>> 
>> I wanted to mention a pet peeve of mine, but I see from Wikipedia that
>> it's becoming accepted to use O(f) in this way.  But in case there is
>> some chance save the old meaning, I'll just say that when I leaned about
>> it, Big-O was only an (asymptotic) upper bound, so the function called
>> small is also O(2^n), and the one called big might be O(n^3).  (A lower
>> bound was given by Omega and both bounds by Theta.)
>
> What you learned is still true. I'm abusing notation slightly which is
> sadly a bad habit I've picked up and is a bit common:
> <https://en.wikipedia.org/wiki/Big_O_notation#Matters_of_notation>
>
>> > small(1000) // 1 billion steps to complete
>> > big(1000) // 1 x 10^301 steps to complete
>> 
>> Or almost any other number of steps, surely?  The order of growth says
>> only that steps(small(2*x)) ~ 8*steps(small(x)).
>
> Any *fewer* number of steps, yes.

Why only fewer?  There's no reason that small(1000) might not take 2
billion steps and/or big(1000) might take 10^500 steps.  You can't tell
anything about the number of steps taken by one call when all you know
is the order of growth.

<snip>
-- 
Ben.

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

#32693

On Saturday, March 4, 2017 at 6:29:12 PM UTC-6, Ben Bacarisse wrote:

> Why only fewer? There's no reason that small(1000) might not take 2
> billion steps and/or big(1000) might take 10^500 steps.

Because it is true by definition in this case (which is why I left out the body of the functions).

>  You can't tell anything about the number of steps taken by one call when all you know is the order of growth.

You can, which is why it is used. It is an abstraction and classification of algorithms.

Big-O states that the number of steps will be at-most that value, but may be less. If I said Θ(n) then it would be exactly n.

if both small() and big() were simply for-loops that incremented some value and returned, then you could state that the running time would be exactly the order of growth. Now if you allowed continue or break statements in the loop then you would know that in the worst case scenario it would not execute MORE than the order of growth, but may execute fewer.

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

#32694

"Michael Haufe (TNO)" <tno@thenewobjective.com> writes:

> On Saturday, March 4, 2017 at 6:29:12 PM UTC-6, Ben Bacarisse wrote:
>
>> Why only fewer? There's no reason that small(1000) might not take 2
>> billion steps and/or big(1000) might take 10^500 steps.
>
> Because it is true by definition in this case (which is why I left out
> the body of the functions).

I don't follow.  By definition of what?

>>  You can't tell anything about the number of steps taken by one call when all you know is the order of growth.
>
> You can, which is why it is used. It is an abstraction and
> classification of algorithms.
>
> Big-O states that the number of steps will be at-most that value, but
> may be less. If I said Θ(n) then it would be exactly n.

No, that's not right.  I'm pretty sure you know the definitions so I'm
not sure what the source of the confusion is.

> if both small() and big() were simply for-loops that incremented some
> value and returned, then you could state that the running time would
> be exactly the order of growth. Now if you allowed continue or break
> statements in the loop then you would know that in the worst case
> scenario it would not execute MORE than the order of growth, but may
> execute fewer.

You didn't describe the function.  You just said that small(1000) takes
a billion steps and can take fewer but can't take more.  Given a full
description of small we probably don't need Big-O at all; we could just
write the number of steps as a function of n.

But without knowing what small is doing -- knowing only that it's order
of growth is O(n^3) the number of steps taken for any one n is entirely
unknown.  That's that position I was in when I said that.

-- 
Ben.

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

#32700

Ben Bacarisse wrote:
> "Michael Haufe (TNO)" writes:
> 
> > Ben Bacarisse wrote:
> >
> >> Why only fewer? There's no reason that small(1000) might not take 2
> >> billion steps and/or big(1000) might take 10^500 steps.
> >
> > Because it is true by definition in this case (which is why I left out
> > the body of the functions).
> 
> I don't follow.  By definition of what?

I stated the limiting behavior on the functions:

// O(n^3)
function small(n){ ... }

// O(2^n)
function big(n){ ... } 

> >>  You can't tell anything about the number of steps taken by one call when all you know is the order of growth.
> >
> > You can, which is why it is used. It is an abstraction and
> > classification of algorithms.
> >
> > Big-O states that the number of steps will be at-most that value, but
> > may be less. If I said Θ(n) then it would be exactly n.
> 
> No, that's not right.  I'm pretty sure you know the definitions so I'm
> not sure what the source of the confusion is.

Big-O is the upper-bound specifically. Whatever the input,
the resulting time will not exceed this bound by definition,
otherwise it wouldn't be the upper bound.

> > if both small() and big() were simply for-loops that incremented some
> > value and returned, then you could state that the running time would
> > be exactly the order of growth. Now if you allowed continue or break
> > statements in the loop then you would know that in the worst case
> > scenario it would not execute MORE than the order of growth, but may
> > execute fewer.
> 
> You didn't describe the function.  You just said that small(1000) takes
> a billion steps and can take fewer but can't take more.  Given a full
> description of small we probably don't need Big-O at all; we could just
> write the number of steps as a function of n.

The point is that it doesn't matter if the upper bound is known.
It's an abstraction.

> But without knowing what small is doing -- knowing only that it's order
> of growth is O(n^3) the number of steps taken for any one n is entirely
> unknown.  That's that position I was in when I said that.

What is known is that whatever it takes to perform it's duty it won't
be MORE than O(n^3).

If you knew it would take AT LEAST as long or precisely as long,
you would use different notations:

<https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations>

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

#32702

"Michael Haufe (TNO)" <tno@thenewobjective.com> writes:

> Ben Bacarisse wrote:
>> "Michael Haufe (TNO)" writes:
>> 
>> > Ben Bacarisse wrote:
>> >
>> >> Why only fewer? There's no reason that small(1000) might not take 2
>> >> billion steps and/or big(1000) might take 10^500 steps.
>> >
>> > Because it is true by definition in this case (which is why I left out
>> > the body of the functions).
>> 
>> I don't follow.  By definition of what?
>
> I stated the limiting behavior on the functions:
>
> // O(n^3)
> function small(n){ ... }
>
> // O(2^n)
> function big(n){ ... }

That gives the asymptotic upper bound.  You can't say anything about
small(1000) from the fact that small(n) is O(n^3).

Here are two other function that are O(n^3):

function small1(n) { if n < 1000000 then return 1 else return small(n) }

function small2(n) { repeat 99 times small(n); return small(n) }

Knowing only the asymptotic upper bound of n^3, you can't say anything
about the number of steps taken by small1(1000) or small2(1000).

>> >>  You can't tell anything about the number of steps taken by one call when all you know is the order of growth.
>> >
>> > You can, which is why it is used. It is an abstraction and
>> > classification of algorithms.
>> >
>> > Big-O states that the number of steps will be at-most that value, but
>> > may be less. If I said Θ(n) then it would be exactly n.
>> 
>> No, that's not right.  I'm pretty sure you know the definitions so I'm
>> not sure what the source of the confusion is.
>
> Big-O is the upper-bound specifically. Whatever the input,
> the resulting time will not exceed this bound by definition,
> otherwise it wouldn't be the upper bound.

It's not an upper bound in that sense -- it's the asymptotic upper
bound, up to a constant factor.  It states (in this case) that there is
some constant C and some integer M such that

  steps_taken_by(small(k)) > C*k^3 for all k > M.

small(1000) can take *any* finite number of steps at all despite knowing
that it's O(n^3).

<snip>
>> But without knowing what small is doing -- knowing only that it's order
>> of growth is O(n^3) the number of steps taken for any one n is entirely
>> unknown.  That's that position I was in when I said that.
>
> What is known is that whatever it takes to perform it's duty it won't
> be MORE than O(n^3).
>
> If you knew it would take AT LEAST as long or precisely as long,
> you would use different notations:
>
> <https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations>

I really do know what these notations mean.  None of them can tell you
anything about the cost of a single call like small(1000).

-- 
Ben.

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

#32703

Ben Bacarisse wrote:

> "Michael Haufe (TNO)" <tno@thenewobjective.com> writes:
>> Big-O is the upper-bound specifically. Whatever the input,
>> the resulting time will not exceed this bound by definition,
>> otherwise it wouldn't be the upper bound.
> 
> It's not an upper bound in that sense -- it's the asymptotic upper
> bound, up to a constant factor.  It states (in this case) that there
> is some constant C and some integer M such that
> 
>   steps_taken_by(small(k)) > C*k^3 for all k > M.

No, it does not.
 
-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | <http://PointedEars.de/es-matrix>
<https://github.com/PointedEars> | <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | Please do not cc me./Bitte keine Kopien per E-Mail.

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

#32704

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Ben Bacarisse wrote:
>
>> "Michael Haufe (TNO)" <tno@thenewobjective.com> writes:
>>> Big-O is the upper-bound specifically. Whatever the input,
>>> the resulting time will not exceed this bound by definition,
>>> otherwise it wouldn't be the upper bound.
>> 
>> It's not an upper bound in that sense -- it's the asymptotic upper
>> bound, up to a constant factor.  It states (in this case) that there
>> is some constant C and some integer M such that
>> 
>>   steps_taken_by(small(k)) > C*k^3 for all k > M.

  steps_taken_by(small(k)) < C*k^3 for all k > M.

(Some people use <= and >= for one or other but that makes no difference.)

> No, it does not.

Indeed, a typo.  Surely just pointing out the swapped comparison would
have been more helpful?  Anyway, thanks for noticing and if there is
anything else, maybe you could say what?

-- 
Ben.

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

#32705

Ben Bacarisse wrote:

> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>> Ben Bacarisse wrote:
>>> "Michael Haufe (TNO)" <tno@thenewobjective.com> writes:
>>>> Big-O is the upper-bound specifically. Whatever the input,
>>>> the resulting time will not exceed this bound by definition,
>>>> otherwise it wouldn't be the upper bound.
>>> It's not an upper bound in that sense -- it's the asymptotic upper
>>> bound, up to a constant factor.  It states (in this case) that there
>>> is some constant C and some integer M such that
>>>   steps_taken_by(small(k)) > C*k^3 for all k > M.
> 
>   steps_taken_by(small(k)) < C*k^3 for all k > M.
> 
> (Some people use <= and >= for one or other but that makes no difference.)

Yes, it does.
 
>> No, it does not.
> 
> Indeed, a typo.  Surely just pointing out the swapped comparison would
> have been more helpful?

No, blankly, firmly, and concisely denying your *unsubstantiated claim* made 
you think more, caused less noise, and saved me more time, in total.  While 
it required you to invest the time that you thought you could save and still 
get away with it, shifting the burden of proof.

“The amount of energy necessary to refute bullshit is an order of magnitude 
bigger than to produce it.” (Alberto Brandolini, programmer, 2014)

> Anyway, thanks for noticing

You’re welcome.

> and if there is anything else, maybe you could say what?

Maybe.  Or maybe you should learn how to ask questions the smart way, and 
how to post on topic.

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | <http://PointedEars.de/es-matrix>
<https://github.com/PointedEars> | <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | Please do not cc me./Bitte keine Kopien per E-Mail.

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

#32706

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
<snip>
> Maybe.  Or maybe you should learn how to ask questions the smart way, and 
> how to post on topic.

Why are you posting on this topic?

-- 
Ben.

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

#32707

Ben Bacarisse wrote:

> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>> Maybe.  Or maybe you should learn how to ask questions the smart way, and
>> how to post on topic.
> 
> Why are you posting on this topic?

(You have destroyed the context of my statement.)

Obviously, to point out false, unsubstantiated claims in a discussion
that I consider off-topic here, too.

Why do you people keep feeding those Google Groups trolls?

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | <http://PointedEars.de/es-matrix>
<https://github.com/PointedEars> | <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | Please do not cc me./Bitte keine Kopien per E-Mail.

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

#32708

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Ben Bacarisse wrote:
>
>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>> Maybe.  Or maybe you should learn how to ask questions the smart way, and
>>> how to post on topic.
>> 
>> Why are you posting on this topic?
>
> (You have destroyed the context of my statement.)
>
> Obviously, to point out false, unsubstantiated claims in a discussion
> that I consider off-topic here, too.

That's what I was doing.  Why are the rules different for you?

> Why do you people keep feeding those Google Groups trolls?

Michael Haufe is not a Google Groups troll.  He replied to someone
matching that description, but I did not.  You could have pointed out
the lack or topicality or any number of false unsubstantiated claims
long before but it seems it seems to be me who fascinates (or maybe just
irritates) you enough to do that.

-- 
Ben.

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

#32709

Ben Bacarisse wrote:

> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>> Ben Bacarisse wrote:
>>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>>> Maybe.  Or maybe you should learn how to ask questions the smart way,
>>>> and how to post on topic.
>>> Why are you posting on this topic?
>> (You have destroyed the context of my statement.)
>>
>> Obviously, to point out false, unsubstantiated claims in a discussion
>> that I consider off-topic here, too.
> 
> That's what I was doing.

You were doing both less and more than that, and you know it.

> Why are the rules different for you?

They are not.  It is a matter of dosage, so to speak.  What does
this discussion have to do with the topic of this newsgroup *now*?
 
>> Why do you people keep feeding those Google Groups trolls?
> 
> Michael Haufe is not a Google Groups troll.

I did not say that he were.

> He replied to someone matching that description,

Exactly.

> but I did not.  You could have pointed out the lack or topicality or any
> number of false unsubstantiated claims long before but it seems it seems
> to be me who fascinates (or maybe just irritates) you enough to do that.

You are overrating the importance of Usenet and yourself to me.

Contrary to common misconception, I do have a life.
 
F'up2 poster

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | <http://PointedEars.de/es-matrix>
<https://github.com/PointedEars> | <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | Please do not cc me./Bitte keine Kopien per E-Mail.

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

#32710

On 07-03-17 21:07, Thomas 'PointedEars' Lahn wrote:

>> but I did not.  You could have pointed out the lack or topicality or any
>> number of false unsubstantiated claims long before but it seems it seems
>> to be me who fascinates (or maybe just irritates) you enough to do that.
>
> You are overrating the importance of Usenet and yourself to me.
>
> Contrary to common misconception, I do have a life.

Do you? Then why don't you spend more time on it?

"...blankly, firmly, and concisely denying your *unsubstantiated claim* made
you think more, caused less noise, and saved me more time, in total."

How much time did you really save considering those three extra replies you
gave after the "no, it does not"? Seems to me like you made the wrong
decision somewhere.

-- 
Flinke Flip

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

#32736

Ben Bacarisse wrote:

> That gives the asymptotic upper bound.  You can't say anything about
> small(1000) from the fact that small(n) is O(n^3).
> 
> Here are two other function that are O(n^3):
> 
> function small1(n) { if n < 1000000 then return 1 else return small(n) }
> 
> function small2(n) { repeat 99 times small(n); return small(n) }
> 
> Knowing only the asymptotic upper bound of n^3, you can't say anything
> about the number of steps taken by small1(1000) or small2(1000).

> I really do know what these notations mean.  None of them can tell you
> anything about the cost of a single call like small(1000).

I read back through our discussion and did a refresher on some notes and I think we're talking towards two different but related things.

What I was trying to state was that any multiple of the growth rate of a function is irrelevant as they fall into the same category and therefore I can ignore what that multiple is:

f(x) = x^2 + 2x + 1
g(x) = 4x^2
h(x) = x^2

O(f(x)) = O(g(x)) = O(h(x)) = O(x^2)

If I understand your argument correctly, you're saying that it may be true that f(x) is O(x^2) eventually, but at some points in the domain it can be far greater than that which wouldn't fall into such a categorization, such as:

f(n) = n^2, n >= 1000
f(n) = n^9, n <  1000

I wasn't sure of the answer to this, so I reviewed one of my Algorithms texts [1] and surprisingly on page 45 it has a graph and description which reflects this very issue.

What we both overlooked (or forgot) is that O(f(n)) is defined with a minimum constraint  as part of the definition that would exclude those lower values. So in the above function it would still be considered O(x^2). From p. 47 of the text:

O(g(n)) = {f(n): there exist positive constants c and n0 such that 
           0 <= f(n) <= c*g(n) for all n >= n0 }

In other words, the larger portion is chopped off. Here's a picture of the graph:

<http://thenewobjective.com/cljs/asymptotic-notation.jpg>

[1] <https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844>

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

#32774

"Michael Haufe (TNO)" <tno@thenewobjective.com> writes:

> Ben Bacarisse wrote:
>
>> That gives the asymptotic upper bound.  You can't say anything about
>> small(1000) from the fact that small(n) is O(n^3).
>> 
>> Here are two other function that are O(n^3):
>> 
>> function small1(n) { if n < 1000000 then return 1 else return small(n) }
>> 
>> function small2(n) { repeat 99 times small(n); return small(n) }
>> 
>> Knowing only the asymptotic upper bound of n^3, you can't say anything
>> about the number of steps taken by small1(1000) or small2(1000).
>
>> I really do know what these notations mean.  None of them can tell you
>> anything about the cost of a single call like small(1000).
>
> I read back through our discussion and did a refresher on some notes
> and I think we're talking towards two different but related things.

Probably.

> What I was trying to state was that any multiple of the growth rate of
> a function is irrelevant as they fall into the same category and
> therefore I can ignore what that multiple is:
>
> f(x) = x^2 + 2x + 1
> g(x) = 4x^2
> h(x) = x^2
>
> O(f(x)) = O(g(x)) = O(h(x)) = O(x^2)
>
> If I understand your argument correctly, you're saying that it may be
> true that f(x) is O(x^2) eventually, but at some points in the domain
> it can be far greater than that which wouldn't fall into such a
> categorization, such as:
>
> f(n) = n^2, n >= 1000
> f(n) = n^9, n <  1000

I was saying you can't say anything about a single value of f from
knowing only the order.  If we know if is O(n^2) f(1000) could be 1, 99,
1x10^103 or -45.  Also f(2000) could be 17, 1,000,000 or 0.  You gave a
single value and said that it could be lower but not higher (because O
is an upper bound).  But f can take any values at all at any of a
finite set of points and still be O(n^2).

> I wasn't sure of the answer to this, so I reviewed one of my
> Algorithms texts [1] and surprisingly on page 45 it has a graph and
> description which reflects this very issue.
>
> What we both overlooked (or forgot) is that O(f(n)) is defined with a
> minimum constraint as part of the definition that would exclude those
> lower values. So in the above function it would still be considered
> O(x^2). From p. 47 of the text:
>
> O(g(n)) = {f(n): there exist positive constants c and n0 such that 
>            0 <= f(n) <= c*g(n) for all n >= n0 }
>
> In other words, the larger portion is chopped off.

I don't think I forgot or overlooked that.  It was the crux of what I
was trying to say.

<snip>
-- 
Ben.

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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.javascript

csiph-web