```Subject: Re: Mergesort: why's it efficient?
From: Erik Naggum <nobody@naggum.no>
Date: 1996/12/06
Newsgroups: comp.lang.c++,comp.sys.mac.programmer.help,comp.lang.lisp
Message-ID: <3058824781104480@naggum.no>

* Dann Corbit
| If the problem is tiny, it may not matter what sort of algorithm, since
| all will finish in a blink.  If the problem is huge, then it matters
| enormously, because for some problem size, O(N*log(N)) will always be
| better than O(n^2).

it appears that many people don't undertand the O notation.  O indicates
complexity, not execution speed.  the execution speed depends on a constant
factor that is insignificant compared to the variable factor as it grows
without bound.  a function of complexity O(n log n) may have a constant
factor (k) that makes execution time (or other resources) _higher_ than a
function of complexity O(n^2) with a much smaller constant (c) as long as
the relation

k       n
--- >> -----
c     log n

holds.  however, your statement that O(n log n) will _always_ be better
than O(n^2) does not hold, precisely because of the possibility of the
above relation.

since Andrew Koenig surprised many by limiting n and then arguing how
insignificant log n is compared to n, as if this is anything but obvious,
others have followed in his muddled footsteps and also conveniently forget
the constant factor or the actual meaning of the O notation.  I'm frankly
amazed that this is possible for even half-educated computer scientists.

the O notation does _not_ indicate execution time.  the O notation is the
_simplest_ function that yields an upper bound on the _relation_ between
the length of the input and the execution time (or space).

I recommend that Andrew Koenig and others who have been confused by him
read Alfred V. Aho and Jeffrey D. Ullman's excellent book "Foundations of
Computer Science" (Computer Science Press, 1992; ISBN 0-7167-8233-2), which
has grown out of the course CS109 -- Introduction to Computer Science at
Stanford University.  the topic of chapter 3 is the running time of
programs.  section 3.10 specifically analyses merge sort.  it should be
instructive to more than the target audience of students, and any
programmer worth his salt _should_ be able to understand this chapter with
little effort.  in particular, their treatment of constants and of the
simplification involved in the O notation is fundamental knowledge and
_should_ not come as a surprise to anyone who has been following these
discussions.  _please_ take the time to look up this book.  (Dr. Aho and
Dr. Ullman have both worked at Bell Labs, which is why I chose this
textbook over many other candidates.  this will hopefully make it harder
for Andrew Koenig to ignore them, as he is wont to do for most everything
else shown to correct or contradict his inaccurate statements.)

#\Erik
--