Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.lang.javascript
Subject: Re: Update only if not already in array
Date: Mon, 27 Mar 2017 22:48:52 +0100
Organization: A noiseless patient Spider
Lines: 42
Message-ID: <87lgrq4chn.fsf@bsb.me.uk>
References: <dd6d3d32-1e0b-4002-93ea-90c28f99f1c2@googlegroups.com> <72c9bb07-427c-4256-bc82-0b0a3acd6cc5@googlegroups.com> <XnsA72E14CC5889eejj99@194.109.6.166> <8e90e371-950e-4774-89f4-1c54566745fa@googlegroups.com> <20ca53b3-e664-4d34-86ec-1bc0e5fb4b1e@googlegroups.com> <87o9xhjb00.fsf@bsb.me.uk> <8fae31a5-24ba-46ac-a746-299a4eb57671@googlegroups.com> <87efyckbg4.fsf@bsb.me.uk> <6758a153-c068-4bbb-b890-52bc05066870@googlegroups.com> <8760jok1m3.fsf@bsb.me.uk> <3aa0dc8d-a808-4583-809c-c74fffda0e08@googlegroups.com> <87mvczhiq5.fsf@bsb.me.uk> <e9f3a0ca-0a50-40d2-a99b-af2fb982d756@googlegroups.com> <8737ep3o6e.fsf@bsb.me.uk> <c6caee16-30a8-411a-b87c-7ea079839164@googlegroups.com> <8737eev420.fsf@bsb.me.uk> <ae2eab05-fbc3-474a-981d-f155f458c8c7@googlegroups.com> <87inn9ubhr.fsf@bsb.me.uk> <68caca55-421a-4642-b1d5-59365978f0ba@googlegroups.com> <87zigis5s9.fsf@bsb.me.uk> <be758927-ea10-4645-96e1-8f0aee22e8f2@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="5c935bd40c654498dcebf2ac621c12b5"; logging-data="22590"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18PG8nQbnWGdiwhDrPfNmSIp7ljAgWe3hM="
Cancel-Lock: sha1:reqBaXMOw8Xb5X4ZUcXRRuKbpZk= sha1:NfYAPg7PEjLUpQBV9VK7cZKat2g=
X-BSB-Auth: 1.477353da2da74c07e538.20170327224852BST.87lgrq4chn.fsf@bsb.me.uk
Xref: csiph.com comp.lang.javascript:32856

"Michael Haufe (TNO)" <tno@thenewobjective.com> writes:

> Ben Bacarisse wrote:
>
>> Give me a few values for f(n) (just list them: f(0) = ?, f(6) = ? and so
>> on) for which you can be *certain* than f is not O(n^2).
>> 
>> You seem to be saying that f(5) = 125, f(6) =
>> 808281277464764060643139600456536293376 means that f can't be O(n^2) but
>> that's not so.  You can no idea what happens for n > 6.  f might even be
>> O(1).

It might help if you commented on this part.  You seemed to be saying
that certain values for f (at some finite from the domain) were
incompatible with some big-O behaviours.  Hence I asked for an example:
some finite set of values for f that shows it not to be O(n^2).

> Difference across machines and the same machine of course can occur,
> but that doesn't prevent one from comparing the quality of an
> algorithm against another nor against itself when modified.

I'm talking about mathematical functions and a mathematical notation
that describes how function may or may not behave.

<snip>
> Determining the category of a function is accomplished by evaluating
> it's components. For instance:
> "primitive" operations are considered O(1); In other words 1-step

This is true for algorithms, yes, but the notation is more general than
that.  (I don't think this is the source of any confusion though.)

<snip example>
> If this doesn't help, then I still don't understand where we missing
> each other

I'm not sure how it could help.  If you agree that any finite set of
function values is compatible with that function being, say, O(n^2) then
we are in agreement.  You seemed to be saying otherwise at one point.

-- 
Ben.