Re: A very basic thing I don't get

[Dirk Laurie <dpl@...>]

On Sun, Oct 02, 2011 at 11:33:50PM +0200, Pascal J. Bourguignon wrote:
> Roberto Ierusalimschy <roberto@inf.puc-rio.br> writes:
> 
> >> [...] but thinking of them as _either_ a linear O(1) structure
> >> _or_ a O(N log N) map is a mistake. [...]
> >
> > Just a detail: both arrays and maps are O(1) in space, and both are
> 
> So when I add one million entries to an array it still takes the same
> space as when I have only one entry.  Interesting.  Perhaps I'll have an
> entry for each star in the universe...
> 

For the sake of the poor newbies who do not realize that Pascal is
being sarcastic: Roberto means "O(1) per item", of course. 

D.