Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.javascript > #32777
Show key headers only | View raw
"Michael Haufe (TNO)" <tno@thenewobjective.com> writes:
> Ben Bacarisse wrote:
>
>> 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).
>
> If you meant at a point less than n0, I agree per the definition.
No, even at a point above n0 because there is also c to consider. Take,
for example, n0 = 0 -- i.e. there is some c such that f(n) < c*n^2 for
all n >= 0. Any finite set of values for f(n) can *still* be
accommodated.
(Actually even that's a rather limited description since the notation
applies to functions in real analysis. In fact, even an infinite set of
arbitrary values for f can be accommodated provided they occur over a
bonded region of the domain.)
>> > 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.
>
> If you meant below n0, then that wasn't clear to me at the time.
No, I meant above or below n0. You simply can't say anything about any
finite set of values of f(n), knowing only that f is O(n^2).
--
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