Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.javascript > #32694
Show key headers only | View raw
"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.
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