Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.lang.javascript Subject: Re: Update only if not already in array Date: Thu, 16 Mar 2017 03:49:36 +0000 Organization: A noiseless patient Spider Lines: 47 Message-ID: <87inn9ubhr.fsf@bsb.me.uk> References: <567cadf8-91e1-4e1d-9183-09b60658ec39@googlegroups.com> <72c9bb07-427c-4256-bc82-0b0a3acd6cc5@googlegroups.com> <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> <8737ep3o6e.fsf@bsb.me.uk> <8737eev420.fsf@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx02.eternal-september.org; posting-host="368b5322df020f7350229613c200b4e1"; logging-data="1798"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19i/Lz3/pHPHVjNx76sY8P5q2eOg0xKomE=" Cancel-Lock: sha1:O24Iz7VfSNpNJFfzo20ieadj1EU= sha1:4KuxDDFnNlF5MUTcYqVI/ouImFA= X-BSB-Auth: 1.66be3517a766d7247489.20170316034936GMT.87inn9ubhr.fsf@bsb.me.uk Xref: csiph.com comp.lang.javascript:32777 "Michael Haufe (TNO)" 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.