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: Sun, 05 Mar 2017 00:29:08 +0000
Organization: A noiseless patient Spider
Lines: 40
Message-ID: <8760jok1m3.fsf@bsb.me.uk>
References: <dd6d3d32-1e0b-4002-93ea-90c28f99f1c2@googlegroups.com> <b3d9b920-6193-4517-ab24-c776174eb9a1@googlegroups.com> <a196f2b6-517b-4082-829d-b6a30bbbddac@googlegroups.com> <fc4d576b-7014-4443-b6fc-f8db28aa0da7@googlegroups.com> <f8e6263d-08e6-46c0-b170-6a42c0b7b9fa@googlegroups.com> <XnsA72D84A6292C9eejj99@194.109.6.166> <ab53c3c5-cc95-44a5-8250-de3f272fa8a7@googlegroups.com> <XnsA72DBA8A7DAA8eejj99@194.109.6.166> <567cadf8-91e1-4e1d-9183-09b60658ec39@googlegroups.com> <XnsA72DF106C4931eejj99@194.109.6.166> <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>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="1fb33df81b78475579caa0e7e068bede"; logging-data="21038"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19qYU2LNwJ7n6Qr8D2hdQrSqTr1LQ3S8FY="
Cancel-Lock: sha1:h5OhaUeWDtj/39VhxWLWVsoB2xA= sha1:FrxqZZwPdV8eHEUFc4fripPyAq0=
X-BSB-Auth: 1.fcf13a6c150f4086cc88.20170305002908GMT.8760jok1m3.fsf@bsb.me.uk
Xref: csiph.com comp.lang.javascript:32690

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