From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=BAYES_00,FORGED_HOTMAIL_RCVD2, FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,f6c360ce344b2364 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,CP1252 Received: by 10.68.223.40 with SMTP id qr8mr2421351pbc.0.1340348305378; Thu, 21 Jun 2012 23:58:25 -0700 (PDT) Path: l9ni5983pbj.0!nntp.google.com!news1.google.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Austin Obyrne Newsgroups: comp.lang.ada Subject: Re: My Invention of "Bug Sort". Date: Thu, 21 Jun 2012 23:52:11 -0700 (PDT) Organization: http://groups.google.com Message-ID: References: <3852c348-a728-44ed-b065-c8a596c1e235@googlegroups.com> <698085ff-6ca3-4a0e-b963-11bdcf11e6b5@googlegroups.com> NNTP-Posting-Host: 31.52.108.135 Mime-Version: 1.0 X-Trace: posting.google.com 1340348305 3340 127.0.0.1 (22 Jun 2012 06:58:25 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Fri, 22 Jun 2012 06:58:25 +0000 (UTC) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=31.52.108.135; posting-account=pmkN8QoAAAAtIhXRUfydb0SCISnwaeyg User-Agent: G2/1.0 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Date: 2012-06-21T23:52:11-07:00 List-Id: On Thursday, June 21, 2012 7:45:21 PM UTC+1, Jeffrey Carter wrote: > On 06/21/2012 04:50 AM, Austin Obyrne wrote: > > > > In general, > > > > A change of base in logarithms: > > > > Log(base(a)M =3D Log (base(b))M / Log (base(b))'a'. > > > > Applying that,In particular here, > > > > Ln of N =3D Log2N / Ln 2 >=20 > No. log2 N =3D ln N / ln 2, so ln N =3D log2 N =95 ln 2. Not that it matt= ers to Big-O=20 > notation. >=20 > > Unless it is true that there is some constant incorporated in O that ve= rifies this, then > > > > N(Ln N) /=3D N(Log2 N) > > > > Which is it? > > > > On face value it appears totally incorrect arithmetically, I'm surprise= d that such an anomaly would be acceptable. >=20 > Big-O notation is about the order of the complexity, not its exact value.= If you=20 > have a super fast algorithm that only does 1 pass over the data, it takes= time=20 > proportional to N. A slower algorithm that makes 2 passes over the data t= akes=20 > time proportional to 2N. Both have time complexity of O(N); a constant fa= ctor=20 > doesn't affect the Big-O value. >=20 > Another way to think about it is that Big-O indicates how the time requir= ed=20 > increases as N increases, not what the time is for a specific value of N. >=20 > --=20 > Jeff Carter > "Death awaits you all, with nasty, big, pointy teeth!" > Monty Python & the Holy Grail > 20 >=20 > --- Posted via news://freenews.netfront.net/ - Complaints to news@netfron= t.net --- Must check out my change of base algorithm sometime soon. But as you point out this is not absolute but relative conjecture -i.e. its= the order of the rate of change that is meaningful but more as a philosoph= y than a mathematicaly computed result - i.e. There is no unit of complexit= y as far as I can see ??? Austin O'Byrne