*From*: Leonard Mada <discoleo gmx net>*To*: gnumeric-list gnome org*Subject*: Re: Median: Oasis and Fast Sorting Algorithm*Date*: Sat, 10 Feb 2007 20:27:13 +0200

Sorry, I noticed, I made 2 small errors: 1. search inside array: log[(n/2)!] << log[(n/4)^(n/2)] = n/2 * log(n/4) !!! 2. move array: log[(n/4)!] << log[(n/8)^(n/4)] = n/4 * log(n/8) !!! This is because (n-k) * k is always < (n/2)^2 and is equal only and only when k = n/2!!! (where k = 0::n) In this way: O(...) << 5/4 * n * log(n) -5/4 * n -1 Please note, that the approximations presented at 1 and 2 are very conservative: 10! / 5^10 = 0.4 12! / 6^12 = 0.2 14! / 7^14 = 0.13 So basically, the terms: log[(n/2)!] are always much less than n/2 * log(n/4); [<< means much less] For really big numbers, even my previous formula was correct, with n/4 instead of n/2. Andreas J. Guelzow wrote:

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)!] > 140but n/4 * log(n/4) < 81What exactly is << supposed to mean?so, even under the worst assumption, it will be less than n * log(n),assuming this is trueand because log[(n/2-1)!] << log[(n/4)^(n/4)], there will indeed be asignificant difference. I presume, that more realistically, thisalgorithm will be 2 times faster than the corresponding sort and usesonly 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

**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

**Re: Median: Oasis and Fast Sorting Algorithm***From:*Andreas J. Guelzow

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