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

Groups > comp.lang.javascript > #32774

Re: Update only if not already in array

Show all headers | View raw

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

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