Re: LOGO-L> Permutation

[bh@anarres.CS.Berkeley.EDU (Brian Harvey)]

"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.