# Python and Schools

David Eppstein eppstein at ics.uci.edu
Thu Apr 17 18:41:57 CEST 2003

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

```