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