Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.javascript > #32700
| Newsgroups | comp.lang.javascript |
|---|---|
| Date | 2017-03-06 07:50 -0800 |
| References | (16 earlier) <87efyckbg4.fsf@bsb.me.uk> <6758a153-c068-4bbb-b890-52bc05066870@googlegroups.com> <8760jok1m3.fsf@bsb.me.uk> <3aa0dc8d-a808-4583-809c-c74fffda0e08@googlegroups.com> <87mvczhiq5.fsf@bsb.me.uk> |
| Message-ID | <e9f3a0ca-0a50-40d2-a99b-af2fb982d756@googlegroups.com> (permalink) |
| Subject | Re: Update only if not already in array |
| From | "Michael Haufe (TNO)" <tno@thenewobjective.com> |
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>
Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web