Python and Schools

[David Eppstein]

In article <_Fzna.27993$LB6.643892 at news1.tin.it>,
 Alex Martelli <aleax at aleax.it> wrote:

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

A simple example would be an algorithm that takes as input a sequence of 
values that are all (for whatever reason) guaranteed to be integers in 
range(n**2), and tests whether any two of them are the same:

def anysame(seq):
    allocate array A, of dimension n**2, WITHOUT INITIALIZING IT
        (is this possible in pure python?)
    for i,x in enumerate(seq):
        if A[x] is an integer and 0 <= A[x] < i and A[A[x]] == x:
            return True
        A[x] = i
    return False

Initializing A would require too much time, but the algorithm is capable 
of working with an uninitialized array.  The usual trick for reducing 
the memory requirements of such an algorithm is to replace the array by 
a hash table, and of course in Python the hash table (dictionary) based 
duplicate detection algorithm is much more preferable, but this makes 
theoreticians unhappy by turning worst-case time bounds into randomized 
expected time bounds.

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science