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

Groups > comp.lang.javascript > #32702

Re: Update only if not already in array

Show all headers | View raw

"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.

Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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