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: Wed, 15 Mar 2017 17:32:39 +0000 Organization: A noiseless patient Spider Lines: 69 Message-ID: <8737eev420.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> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx02.eternal-september.org; posting-host="7cfa41d0aff51e4cada3e44f3460edba"; logging-data="7337"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+VYk0YtlIVOP+KVhWrrmtZ1QwPIKq0Beo=" Cancel-Lock: sha1:miftx1x2CzuTDjQtia2J7Rdw3O4= sha1:Ex2a/6VZ1swmQurQVow/16r6JHY= X-BSB-Auth: 1.0a60af6ff5b3cab69042.20170315173239GMT.8737eev420.fsf@bsb.me.uk Xref: csiph.com comp.lang.javascript:32774 "Michael Haufe (TNO)" 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. -- Ben.