Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!rpi!leah!bingvaxu!vu0310
From: vu0310@bingvaxu.cc.binghamton.edu (R. Kym Horsell)
Newsgroups: comp.lang.c
Subject: Re:  Sorting Algorithm
Message-ID: <3888@bingvaxu.cc.binghamton.edu>
Date: 24 Aug 90 22:26:17 GMT
References: <wayned.0932@wddami.spoami.com> <3612@goanna.cs.rmit.oz.au> <wayned.0936@wddami.spoami.com>
Reply-To: vu0310@bingvaxu.cc.binghamton.edu.cc.binghamton.edu (R. Kym Horsell)
Organization: SUNY Binghamton, NY
Lines: 17

In article <wayned.0936@wddami.spoami.com> wayned@wddami.spoami.com (Wayne Diener) writes:
\\\
>   If the comparison is quite costly, then for reasonable numbers of N
>   (say 10K to 50K max?) the efficiency of the sort would still be
>   approximately O(N * Log(N)) _even IF the pointer movement is O(N**2)_.

If *part* of an algorithm is O(n**2), and all other parts are ``<''
O(n**2) then the algorithm is O(n**2). The idea is that O signifies the
asymptotic complexity of the algorithm -- for sufficiently large
n the O(n**2) term will dominate other complexity terms regardless of 
how tiny its ``coefficient'' is wrt that of other parts of the complexity
expression.

If you want to talk an algorithm that operates with ``reasonable'' values 
of some parameter then it is a bit misleading to use the O notation.

-Kym Horsell.