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: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
From: adam@irvine.com (Adam Beneschan)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/16
Message-ID: <4v2msb$4a8@krusty.irvine.com>#1/1
X-Deja-AN: 174928231
references: <4umeot$re2@hil-news-svc-2.compuserve.com>
 <dewar.839831192@schonberg> <4v2fb9$lpj@news.utdallas.edu>
organization: /z/news/newsctl/organization
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-16T00:00:00+00:00
List-Id: <comp.lang.ada>


heller@utdallas.edu (Steve Heller) writes:
>dewar@cs.nyu.edu (Robert Dewar) wrote:

 >>Radix sorts are not O(n), the analysis is not that simple. They are
 >>O(kN) where k is the number of radix digits in the numbers, 
 
 >  As I understand it, the O() notation indicates how the time to
 >process varies with the number of elements. E.g., if 1000 elements
 >take 1 second and 2000 elements take 2 seconds to sort, the sorting
 >algorithm is O(n). According to this definition, the distribution
 >counting sort is O(n).

The following definition of O-notation comes from Knuth's _Art of
Compute Programming_, volume 1.  To quote (and I've had to fudge the
notation to get it into ASCII):

    In general, the notation O(f(n)) may be used whenever f(n) is
    a function of the positive integer n; it stands for _a
    quantity which is not explicitly known_, except that its
    magnitude isn't too large.*  Every appearance of O(f(n))
    means precisely this: there is a positive constant M such
    that the number Xn represented by O(f(n)) satisfies the
    condition abs(Xn) <= M * abs(f(n)). . . .

* This last phrase makes more sense in the context of asymptotic
representations, in which it appears in Knuth's book.

More succinctly, from Thomas A. Standish's _Data Structure Techniques_: 

    We say that g(n) = O(f(n)) if there exist two constants K and
    n0 such that abs(g(n)) <= K * abs(f(n)) for all n >= n0.

These definitions only allow for functions of one integer variable;
however, there is no reason they can't be extended to functions of more
than one variable.  I have no idea whether this has been done in
mathematical literature, but I don't see why one can't say

    We say that g(m,n) = O(f(m,n)) if there exist three constants K,
    m0, and n0 such that abs(g(m,n)) <= K * abs(f(m,n)) whenever 
    n >= n0 and m >= m0.

So, going back to Robert's statement, if "k", the number of radix digits
in the numbers, and "N", the number of elements, are allowed to vary
over the entire space of positive integers, then it would be wrong to
say the sort time is O(N).  This is because no value of K that satisfies
the above definition could be found---you could always make "k" large
enough to make the inequality false.  So O(kN) is correct, as Robert
said.  Steve's understanding of O-notation is fine for most practical
purposes, but it's an oversimplification.

                                -- Adam