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.3 required=5.0 tests=BAYES_00,INVALID_MSGID, WEIRD_PORT autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: tanmoy@qcd.lanl.gov (Tanmoy Bhattacharya) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/23 Message-ID: #1/1 X-Deja-AN: 175998715 references: <4v2qkd$40f@news1.mnsinc.com> content-type: text/plain organization: Los Alamos National Laboratory mime-version: 1.0 newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-23T00:00:00+00:00 List-Id: In article dewar@cs.nyu.edu (Robert Dewar) writes: RD: performance for a given value of N, and result in a performance of RD: something like O(N log log N) which doesn't look as good as RD: O(N^1.00000000001) but is in fact faster for any practical data set size. RD: I am confused: O(N log log N) is of course faster than O(N^(1+epsilon)) for every epsilon>0. Proof: lim log N/N^epsilon = lim 1/(epsilon N^epsilon) = 0, and log log N is even slower because by the same proof, lim log log N / log N = 0. So, what was that comment that `it doesn't look as good'? Cheers Tanmoy -- tanmoy@qcd.lanl.gov(128.165.23.46) DECNET: BETA::"tanmoy@lanl.gov"(1.218=1242) Tanmoy Bhattacharya O:T-8(MS B285)LANL,NM87545 H:#9,3000,Trinity Drive,NM87544 Others see , or. -- fax: 1 (505) 665 3003 voice: 1 (505) 665 4733 [ Home: 1 (505) 662 5596 ]