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
_______________________________________________
gnumeric-list mailing list
[email protected]
http://mail.gnome.org/mailman/listinfo/gnumeric-list
