confused about resizing array in Python

[Ruan]

Then how about Python's list?

What is done exactly when list.append is executed?

For list, is there another larger list initialized and the contents from the
old list is copied to it together with the new appended list?



"Roel Schroeven" <rschroev_nospam_ml at fastmail.fm> wrote in message
news:8I5xh.324951$zp2.6359166 at phobos.telenet-ops.be...
> Ruan schreef:
> > My confusion comes from the following piece of code:
> >
> >  memo = {1:1, 2:1}
> > def fib_memo(n):
> > global memo
> > if not n in memo:
> > memo[n] = fib_memo(n-1) + fib_memo(n-2)
> > return memo[n]
> >
> > I used to think that the time complexity for this code is O(n) due to
its
> > use of memoization.
> >
> > However, I was told recently that in Python, dictionary is a special
kind of
> > array and to append new element to it or to resize it, it is in fact
> > internally inplemented by creating another array and copying the old one
to
> > it and append a new one.
>
> That's not correct. Python dictionaries are highly optimized and I
> believe the time complexity is amortized constant (i.e. O(1)) for both
> insertions and lookups.
>
> --
> If I have been able to see further, it was only because I stood
> on the shoulders of giants.  -- Isaac Newton
>
> Roel Schroeven