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
	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: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
From: adam@irvine.com (Adam Beneschan)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/23
Message-ID: <4vkq13$qam@krusty.irvine.com>#1/1
X-Deja-AN: 176045060
references: <01bb8f83$e115a340$87ee6fce@timpent.airshields.com>
 <dewar.840757915@schonberg> <TANMOY.96Aug23111315@qcd.lanl.gov>
organization: /z/news/newsctl/organization
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-23T00:00:00+00:00
List-Id: <comp.lang.ada>


tanmoy@qcd.lanl.gov (Tanmoy Bhattacharya) writes:
 >In article <dewar.840757915@schonberg>
 >dewar@cs.nyu.edu (Robert Dewar) writes:
 ><snip>
 >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

You're right that (N log log N) grows slower than (N^1.00000000001).
This means that there is a constant M such that, for all N > M, 
(N log log N) < (N^1.00000000001).  By doing some calculations, I've
determined M to be somewhere around e^3361885464550.  That's right,
e to the (3.36-trillion)th power.  So if we assumed that the two
constants of proportionality used for O-notation were the same, the 
O(N log log N) algorithm would only be faster if we were planning on
multiplying numbers with at least e^3361885464550 digits.  I suspect
it will be at least ten years before any manufacturers come out with a
computer even capable of storing that many digits in memory.  :-)

I'm just trying to point out how silly this discussion can become when
we try to be strict about the mathematics.  Sure, O(N log log N) is
smaller than O(N^1.00000000001), according to the mathematical
definitions, but (as Robert was trying to say) this tells us
absolutely nothing about which algorithm is better for our purposes.  

Just to continue the silliness, what we've all failed to realize is
that ALL sort algorithms are really O(1).  This is because, for any
sort algorithm, there is a constant M such that

    for N < M,      running time is roughly proportional to N^2 or
                    N^(3/2) or (N log N) or whatever
    for N >= M,     running time is constant (i.e. the time it takes
                    to display "Memory capacity exceeded" and abort)

So according to the mathematical definition of O-notation, the running
time is always O(1).  

                                -- Adam