Re: LOGO-L> Permutation

[George Mills <mills@softronix.com>]

Very good post Brian.

My teacher on Complexity once said.
A slow algorithm is always slow no matter what the machine.

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.
> 
> Jon Bentley has a nice example in which he coded an O(N^3) algorithm in
> optimized Fortran for a Cray supercomputer, and an O(N) algorithm in
> interpreted BASIC for a Radio Shack TRS-80 microcomputer.  The results:
> 
>                 t1(N) = 3.0 N^3         t2(N) = 19,500,000 N
> 
>         N       CRAY-1 Fortran          TRS-80 Basic
> 
>         10      3.0 microsec            200 millisec
>        100      3.0 millisec            2.0 sec
>       1000      3.0 sec                 20 sec
>      10000      49 min                  3.2 min
>     100000      35 days                 32 min
>    1000000      95 yrs                  5.4 hrs
> 
>                         from _Programming_Pearls_
>                         by Jon Bentley (Addison-Wesley, 1986)
> 
> [The first four lines are actual timed runs; the last two are
> computed extrapolations.]
> 
> ---------------------------------------------------------------
> 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.

-- 
===============================================================
George Mills (mills@softronix.com)
http://www.softronix.com/
The www page contains some very powerful educational software.
Our single most important investment is our kids.
---------------------------------------------------------------
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.