Re: Teaching sorts [was Re: What's the best language to start with?]

[tanmoy@qcd.lanl.gov (Tanmoy Bhattacharya)]

In article <01bb8f1b$ce59c820$32ee6fce@timhome2>
"Tim Behrendsen" <tim@airshields.com> writes:
<snip>
B: I have to admit, I have to side with Szu-Wen.  I've never really
B: thought about this case for the O() notation, but it seems from
B: a purely mathematical standpoint that O(f(n)) means that f(n)
B: is *the* function.  If f(n) happens to be a non-continuous function,

It is not a question of convenience or usefulness: it is a question of
definitions. As is almost universally defined defined, O(n^2+n) and
O(n^2) mean exactly the same, as does

<snip>
B: 
B:     O( (n < 1000) ? n : n^2 )
B: 

and hence when you write it instead of the more easily read O(n^2), it
tells people that you do not know the meaning of O().

B: The latter is not only more useful, but absolutely accurate.

Which is irrelevant. Use, a different notation if you want to invent a
new concept: a concept that is more useful in what you want to do. 

B: AFAIK, there are no limits on the complexity of the Big-Oh
B: function, and no requirement that it be a continuous
B: function.

No, but a complex Big-Oh function has *exactly* the same meaning as a
simpler one in most cases. Calling something a O(f(n)) function means
saying that (This may not be the technical definition: but this
expresses the meaning commonly used):

  1) there exists k and N depending on k such that for all n > N, the
     function in question is bounded in absolute value by by k |f(n)|. 
  2) The minimum such k is non-zero. (This is to prevent a O(n)
     function also being classified as a a O(nlogn) for example).

The notation works quite well in practice: generally what happens is
that for very small n (for n < N in the definition), the `main loop'
is not dominant: there are other stuff like initialization which
dominates the time taken. The big O notation says that we are
interested in the behaviour of the function when such subdominant
pieces are unimportant. In fact, such a division is important because
there is no reason why the ratio of time taken in the loop to the time
taken outside it should be independent of the machine in use: if you
wanted big O notation to be a property of the algorithm and not the
hardware (as long as we stick to a reasonable architecture), you
cannot include subdominant terms in it. Incidentally, the
constant k simply means that it is not important what the units of
measurement are, again serves to make the notation independent of the
precise hardware on which it is being run.

However, there are pathological cases: one such pathological case is
when the initialization (or something similar) takes a large amount of
time. Thus for example, we can thing of an algorithm that takes
0.00001 n (main loop) + 1000 (initialization) amount of time. Now, for
n >> 100000000, the initialization is unimportant: and big O notation
will latch on to that case and call it an O(n) problem. However, in
practice, all that you will ever see for a reasonable n is the
initialization time, and hence, in practice, it will look much like an
O(1) problem.

Similarly, sometimes the time taken to really do a problem (say adding
two numbers) is proportional to the number of digits in the number:
i.e. to log n. However, on most hardware, the time taken to do this is
a constant, albeit with a limit to the size of numbers it can add. In
such cases, again, the observed complexity will be O(1), whereas
truly, the complexity is O(logn).

But, these caveats about order O is the penalty we pay for using an
useful concept. The defintion you called more useful, most will find
*less* useful: to use such a concept for a sorting routine, one would
need to know the relative time for a swap and compare on the
particular hardware for example. Giving up the machine independence in
a concept designed to measure abstract algorithmic efficiency is a
stiff price to pay for a perceived usefulness.

Most people instead choose to give you the O() of the algorithm with a
statement pointing out the caveats. I have seen statements that
`addition is O(1) with the caveat that if the numbers really became
big, it would become O(logn)'. Such statements are necessarily
mathematically imprecise, but we know what they mean. And, if, someone
were to question me as to what the precise meaning is, I could of
course phrase it trivially: It would be a fomalization of `what I mean
is that if we enlarge the turing machine with an oracle that can add
arbitrarily large numbers in one move, the algorithm would become O(1)
instead of O(n)'. 

Calling something O(n^2+n) is still an abomination!

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 <gopher://yaleinfo.yale.edu:7700/00/Internet-People/internet-mail>,
<http://alpha.acast.nova.edu/cgi-bin/inmgq.pl>or<ftp://csd4.csd.uwm.edu/pub/
internetwork-mail-guide>. -- <http://nqcd.lanl.gov/people/tanmoy/tanmoy.html>
fax: 1 (505) 665 3003   voice: 1 (505) 665 4733    [ Home: 1 (505) 662 5596 ]