Re: Median: Oasis and Fast Sorting Algorithm

["Andreas J. Guelzow" <aguelzow taliesin ca>]

On Sat, 2007-10-02 at 19:49 +0200, Leonard Mada wrote:


> - move array (with worst algorithm): log[(n/2)!] << log[(n/4)^(n/4)] =
> n/4 * log(n/4)

for n=100    log[(n/2)!]    > 140 
         but n/4 * log(n/4) <  81

What exactly is << supposed to mean?

> so, even under the worst assumption, it will be less than n * log(n), 

assuming this is true

> and because log[(n/2-1)!]  <<  log[(n/4)^(n/4)], there will indeed be a 
> significant difference. I presume, that more realistically, this 
> algorithm will be 2 times faster than the corresponding sort and uses 
> only half the memory.

"2 times faster" means nothing. You are counting artifical actions
assuming that a comparison is the same as moving a memory block. When
you write the real code a small constant factor can easily disappear.
And typically with complex algorithms it will disappear.

Andreas
-- 
Prof. Dr. Andreas J. Guelzow
Dept. of Mathematical & Computing Sciences
Concordia University College of Alberta