Re: Median: Oasis and Fast Sorting Algorithm

[Leonard Mada <discoleo gmx net>]

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)!]    > 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
>