*From*: "Andreas J. Guelzow" <aguelzow taliesin ca>*To*: gnumeric-list gnome org*Subject*: Re: Median: Oasis and Fast Sorting Algorithm*Date*: Sat, 10 Feb 2007 11:03:14 -0700

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

**Follow-Ups**:**Re: Median: Oasis and Fast Sorting Algorithm***From:*Leonard Mada

**References**:**Median: Oasis and Fast Sorting Algorithm***From:*Leonard Mada

**Re: Median: Oasis and Fast Sorting Algorithm***From:*Uri David Akavia

**Re: Median: Oasis and Fast Sorting Algorithm***From:*Leonard Mada

**Re: Median: Oasis and Fast Sorting Algorithm***From:*Uri David Akavia

**Re: Median: Oasis and Fast Sorting Algorithm***From:*Leonard Mada

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