Re: LOGO-L> Permutation

["Tom Lynn" <thl22@cam.ac.uk>]

On 16 Sep 98, at 20:40, Brian Harvey wrote:

> "Tom Lynn" <thl22@cam.ac.uk> writes:
> >  I think this is
> >O(n^2), but as the majority of the checking is done by member it should
> >behave as if it was O(n).
> 
> Probably everyone in this discussion already knows what I'm about to say,
> but it should be here for the record:  A constant factor speedup (such as
> using a C-coded primitive instead of a Logo-interpreted equivalent) can
> outweigh the order of growth up to a point, but for a sufficiently large N
> (that is, for a long enough list) the order of growth will predominate.

True, of course, but a bit of pragmatism is needed too.  It's better to use 
a fast O(n^3) algorithm than a O(1) algorithm with a large overhead if you 
won't be using the algorithm for very large n.

An example was the comparison between pooldeal and your deal.  Pooldeal 
eventually did better (for n > 2000 or so) but I don't think many people 
will really use lists of over 2000 items in Logo, so your deal was more 
practical.

For most Logo algorithms to be useful, I would suggest that performing well 
for small n may be more important than for large n.

Tom (stirring trouble ;)

P.S.
Nice statistics, btw.  I'll store them away for when I'm on the other side 
of this discussion sometime in the future... :)
---------------------------------------------------------------
Please post messages to the Logo forum to logo-l@gsn.org.  Mail
questions about the list administration to logofdn@gsn.org.  To
unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.