Re: Median: Oasis and Fast Sorting Algorithm

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.

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

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]