Python and Schools

[Steven Taschuk]

Quoth Alex Martelli:
> Steven Taschuk wrote:
>    ...
> > trade-off as being between, say, an algorithm which runs in O(n)
> > time but needs O(n^2) memory to do it, and an alternative which
> 
> I don't think there can be any such algorithm -- in O(n) time,
> the algoritm cannot USE more than O(n) memory, so how could it
> NEED it...?  The reverse, sure, but not this way, I think.

Eppstein's given a nice example here, assuming O(1) memory
allocation.  What I had in mind was something much less clever --
just not counting the time to set up ancillary data structures.

A silly example: comparing two strings for lexicographic order.
The obvious character-by-character algorithm is O(len(s)) (where s
is one of the strings -- doesn't matter which).  If, however, the
set of strings which might enter into comparisons during the
execution of the program is fixed and computable beforehand (in
particular, finite), you might precompute the results of all the
n^2 comparisons.  Then comparing two strings is just a lookup in
the table, which might be just O(1).

Of course, it does take O(n^2) time to set up such a table, and
from that point of view you are of course correct.  In practice
that might not matter.

-- 
Steven Taschuk                  staschuk at telusplanet.net
"Telekinesis would be worth patenting."  -- James Gleick