confused about resizing array in Python

[Roel Schroeven]

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