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: Tue, 07 Mar 2017 00:50:33 +0000 Organization: A noiseless patient Spider Lines: 77 Message-ID: <8737ep3o6e.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> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: mx02.eternal-september.org; posting-host="54022d1693a47b06fd1230219a4db6d9"; logging-data="21654"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+HfEv+3FYa4NP9rjlKzmwjmTg2soVIZ6w=" Cancel-Lock: sha1:OQjM/J0q2eKUyVE6lGHbExgs1Xg= sha1:j5AWj6lUZJjbCEYixmtSUkoeePU= X-BSB-Auth: 1.44b735b678c1fa63b531.20170307005033GMT.8737ep3o6e.fsf@bsb.me.uk Xref: csiph.com comp.lang.javascript:32702 "Michael Haufe (TNO)" writes: > Ben Bacarisse wrote: >> "Michael Haufe (TNO)" writes: >> >> > Ben Bacarisse wrote: >> > >> >> 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. >> > >> > Because it is true by definition in this case (which is why I left out >> > the body of the functions). >> >> I don't follow. By definition of what? > > I stated the limiting behavior on the functions: > > // O(n^3) > function small(n){ ... } > > // O(2^n) > function big(n){ ... } 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). >> >> You can't tell anything about the number of steps taken by one call when all you know is the order of growth. >> > >> > You can, which is why it is used. It is an abstraction and >> > classification of algorithms. >> > >> > Big-O states that the number of steps will be at-most that value, but >> > may be less. If I said Θ(n) then it would be exactly n. >> >> No, that's not right. I'm pretty sure you know the definitions so I'm >> not sure what the source of the confusion is. > > Big-O is the upper-bound specifically. Whatever the input, > the resulting time will not exceed this bound by definition, > otherwise it wouldn't be the upper bound. It's not an upper bound in that sense -- it's the asymptotic upper bound, up to a constant factor. It states (in this case) that there is some constant C and some integer M such that steps_taken_by(small(k)) > C*k^3 for all k > M. small(1000) can take *any* finite number of steps at all despite knowing that it's O(n^3). >> But without knowing what small is doing -- knowing only that it's order >> of growth is O(n^3) the number of steps taken for any one n is entirely >> unknown. That's that position I was in when I said that. > > What is known is that whatever it takes to perform it's duty it won't > be MORE than O(n^3). > > If you knew it would take AT LEAST as long or precisely as long, > you would use different notations: > > 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). -- Ben.