need help defining Constant memory requirement

[Andrew Koenig]

"Jani Yusef" <jani at persian.com> wrote in message 
news:d3be1825.0409182100.612a5dcb at posting.google.com...
>I have a HW problem stated as shown at the top of the solution. The
> thing is is that I am not 100% sure wtf constant memory means. Well, I
> think I do but I am confused. Does my solution use contant memory in
> terms of the length of the list i? If so why not and how could I
> change it to be so? I am sure the solution is O(n) since the list must
> only iterated once and the dictionary is O(1), correct?
> Thanks for the help!!

Constant memory means the same as O(1) memory -- in other words, that it is 
possible to place an upper bound on the total amount of memory used (aside 
from the input) regardless of how large the input is.

> #You are given a sequence S of n numbers whose values range from 1 to
> n-1.
> #One of these numbers repeats itself once in the sequence.
> #(Examples: {1 2 3 4 5 6 3}, {4 2 1 2 3 6 5}).
> #Write a function that finds this repeating number using a constant
> #amount of memory and linear time.
> import sys
> i=[1,3,4,5,3]
> tally={}
> for a in i:
>        if tally.has_key(a):
>                print "repeated number is "+str(a)
>                sys.exit(0)
>        else:
>                tally[a]=1
> print "no repeat found"

This program doesn't use constant memory, because tally might conceivably 
have as many as n-1 elements, where n is the number of elements in the 
input.  Therefore the total amount of space needed is O(n), not O(1).

One question you might ask:  Is the entire input sequence available at once? 
Is it permissible to modify its elements?