Re: [AD] Remove the P3D code please!

[Olly Betts <olly@xxxxxxxxxx>]

In message <20010219161237.5241.qmail@xxxxxxxxxx>, tom st denis wri
tes:
>The radix sort is an O(cn) time algorithm where n is the number of
>elements and "c" is the number of radix elements (i.e bits).  The qsort
>is a O(log(n)n) (I think, Knuth Vol3 P122).  So if we have 16-bit
>elements we have 16n vs. log(n)n.  Chances are to get log(n)=16 you
>need n=10^16 (i.e really big).  So qsort is much faster.  for
>example... with 1000 faces (16-bit precision for Z) we have 16*1000 vs
>3*1000 or 16000 vs 3000.  
>
>Radix sorting is over 5 times slower.

You seem to have misunderstood O(...) notation.  O(...) notation says how a
quantity (average case run time here) varies with some variable or variables
describing the input (here, the number of items to sort and the number of
bits in each item).  But the units are arbitrary.

A quicksort routine which takes 10*n*log(n) years is still O(n*log(n)); a
radix sort implementation which takes 2*cn microseconds is still O(cn).  The
`c' here is just telling you that radix sort depends not only on the number
of inputs (n) but also on how many bits they each have (c).

You can't simply feed in numbers and declare that O(n*log(n)) is faster or
slower than O(cn) for n=1000.  What the O(...) notation does tell you here
is that above some value of n the average case of a radix sort will
outperform the average case of a quicksort.  You can't tell anything about
what value of n this happens at from just the O(...) notation - you'd have
to examine the algorithms themselves, or implement both and see.

Another point to note is that worst case for a quicksort is O(n^2) and it
can be quite easy to hit this unless you are carefully with your pivot
picking strategy (often already sorted data is a worst case for quicksort).

Cheers,
Olly